I have noticed this same thing, even though I went outside and tried to get the gps to find me with a direct view of the sky. It probably took about 3 minutes and didn't pull up my exact location, but found one within about a mile, so pretty close eventually.
I seem to have no trouble with the gps when using Google Maps features, but WHERE is starting to annoy me.
Yesterday I did a search for Home Depot and it did not find the location closest to me. I ended up having to go out to my browser and locate the phone number that way instead. WHERE also didn't recognize my zip code when I chose the "set manually" location.
I was a big fan of this app when I first downloaded it, but am becoming disenchanted with its practicality.
Perhaps there is a satellite glitch in the area where I live, but this is what I found yesterday.
BTW, I have a Samsung Galaxy S device- Captivate (att)