I'm having a pretty similar experience.

I have an N810 sitting on a third floor window sill, with a pretty clear line-of-sight to a wide area of sky. The Map application is running, with the GPS dialog open, showing "Searching..." and has been for about 45 minutes now.