Yeah, I got rejected to Minnesota too. =/ I saw the rejected-to-waitlist post before I got rejected and was hopeful that maybe I would somehow end up on the wait-list. Oh well I guess. I hope your situation works out, and you and your SO are still able to live together next year.
When my SO and I set out to apply to PhD programs, we didn't care at all where we ended up, just as long as we ended up somewhere near each other (within an hour or two hours from each other). So we applied to university-rich areas, like southern California, the north east (especially NYC, Philadelphia, and New Jersey). We applied to some midwest schools, which we've both gotten into, just not the same ones. So far, it's not looking good. But then again, we still have several schools left to hear back from.
Good luck with the rest of your programs! I hope you hear good news soon.
Good luck with everything. If it doesn't work out for my SO and me this year, I'll just do international NGO stuff. It's something I've always wanted to do.