I've been three places where I've felt real kinship with the people around me, to varying degrees. I find it when I go to work out; there's a focus amongst everybody in doing something pure and on self-improvement. That's the least I've felt it. I find it among theater people - the real obsessives. Theater is such an odd thing that the people who are drawn to it are very focused on doing as good a job as they can, they're confident enough to have a good time doing so, and they understand how hard it is, so that they welcome most anybody who wants to learn. It was most focused at a summer program I spent a month at, that selected high school students based entirely on talent rather than GPA and resume, and made itself entirely free of charge. I was one of the writers in the program, and everybody in every field was absolutely incredible. Once you get to that sort of group, everybody's interesting and unique and loves everybody else to some degree.
So that's the tried-and-true method: find the places that are pockets of talent. Those places attract more talent and become really focused. If you can't immediately get there, the method I've found works is to just act like yourself. Don't avoid parts of your personality just because other people find them off-putting. That's uncomfortable. Instead, try and focus on doing what you want to do, and find the sorts of people that gravitate towards you based on who you are. I found, actually, that in my senior year of high school the people doing that all found each other, and while that group broke apart again, we had a few really wonderful months where we were all with people we'd never known really well before, where we liked each other not just for intellect but for personal honesty.
That's not as easy a route, depending on what kind of person you are. I'm very sharp-tongued, for instance, and I'm not very interested in most people. That in itself offends some people, or at least makes them indifferent. But the result is that when you are with people, you really value them. I really connected with my roommate - he got me into lifting weights, actually - and a few people on my floor. Some musician/gamer/coder/work-out types. Nobody who's exactly my personality type, but a lot of people who really tolerate each other for who we are. And that's better than pretending friendships and having none.
Despite that, I've got phases. I have some periods where I feel outright hateful hostility towards the people who aren't like me. I usually just keep that inside me, and focus the angst that I've got on working. The first major period of it I wrote a book. After that I wrote a few bursts of poetry and designed a web site. I'm half in the middle of one now and it's really keeping me focused on my work. It helps to focus it outwards at something (though, as a warning, I tried to get rid of it by drinking once and as a result half my floor wouldn't speak to me for months).
I overanalyze friendships to death, to answer your last question. I overanalyze everything. I think that's a good thing. It implies that you're seeking for something meaningful and lasting. If something's not working, then it doesn't hurt to try and change it. Just don't get off to too drastic a start, or you'll burn bridges that you regret burning later.
Hope that helps you! :-)