Yeah, similar situation here as well. I finished my undergrad last spring and spent this year doing "international NGO stuff" while I worked on my applications. My SO is going to graduate college in May and already had a job offer in Minneapolis, so I was hoping to get into Minnesota – it would have made things so much easier! The dream was crushed yesterday...
But no, we ruled out long-distance since we have already done it twice for extended periods of time. I am from Europe and applied to programs only in the US to move closer to my SO, so pretty much whichever school I'll choose to attend, that's where the SO will look for a job.
Hope it'll work out for all of us, one way or another!