I know exactly what you mean. The internet means we become much more accustomed to associating with people with similar interests. I have had a similarly hard time, even having lived all over the US. It's just difficult, especially when your interests are things that are very "independent" -- computers, learning, music (at least for me, since it's not generally the type you can go to a bar and listen to).
The people I'm closest to are all purely coincidental.
Try software competitions maybe? It's really the only place I can think of where I've felt like I could get on with a large portion of the people, but even then I still feel like I have a very different personality.
It's a vicious cycle. I consider myself pretty extroverted, but I just am bored by most people. I'm sure everyone else who I might become friends with has the same problem, and thus none of us ever meet.