I have a great deal of experience with using GPS, and have been quite surprised at how flaky it can sometimes be.
Even with a clear sky and an unobstructed view of it, I've had, on occasion, an incredibly poor signal.
My "On the road and off it too" thread on ipadforums.net goes into some detail concerning the subject.
My jump-to-conclusion guess is that there is nothing wrong with your phone. Give it time to locate the satellites and settle down, at least half an hour in my experience.
You only need 3 satellites to get a fix, but the optimum is 6 or 7. Don't forget, those things are on the move, being in low orbit, so it's not like you are using geo-stationary satellites.