darkbloo: I just had the Nokia 5800 out and tried to reproduce your issue. When you are prompted to Select Connection: are you using a WiFi connection? If so that could be your problem. Have you tried changing the connection from this screen? I noticed that when I have WiFi selected for the connection that I am not able to aquire GPS even when I am in the WiFi range. Please give that a try and let us know how it works.
Thanks!
Michael