What app are using while waiting? Is it Google Maps, Google Nav, or some other app. Does the icon continue to blink the entire time?
I've had to exit out of Google Maps and come back in before to get it to work properly. If the icon is solid, the GPS has locked, but it's like Maps isn't reading it.
If you're icon just sits there blinking, then maybe it's a hardware issue. DL09 seems to have worked for more people than not.
All that said, I have noticed it takes a little bit longer when it's dark, dreary, and heavily overcast in Seattle.