I have the exact same problem (I'm in Minnesota). Sometimes my city pops up. Mostly it'll just say the state though. And if I try to search for it - it doesn't show up at all. It does seem to be pretty good about finding my location when I'm travelling though. This same thing happened with my last phone (Eris Droid) as well.
I've tried tons of things and nothing seems to affect it. It's just random. I almost have to believe it has to do with the Verizon tower or something.