Duke, I feel for you...that sounds really tough. I went through something similar when I moved back to NJ a few years ago, since I hadn't kept in touch with a single person from HS and so didn't know a soul in NJ who wasn't relate to me.
What turned the corner for me was joining a rugby team. I had played in college, and playing again (even though I spent more time warming the bench than scrumming) gave me a group of people to hang with and things to do on weekends. And slowly I developed real friendships on the team, not just "people to be around".
I'm not advocating you take up rugby (though it is an INCREDIBLY social sport, and it's pretty much instant community), but pick your favorite sport and find a team or two. Worst case, put an ad up on Craigslist in your area looking for a team for your favorite sport.
Sports helps because there's an immediate common bond between you and your teammates, AND you get moving and keep in shape. Win-win!