i get lock on within 15 - 30 seconds from a cold start
ive used th sat nav all over the uk and have never had any troubles with it , it works very well indeed ive sold my bluetooth gps and my tomtom unit as my
n95 with garmin mobile xt works very well indeed
maybe your internal antennas are broken , there was a a user on here who took his phone apart and found his gps aerial was touching the side of his phone he moved it away and his gps signal lit up straight away :-)
iam not suggesting you take your phone apart but you could print the info off and take it to a nokia service centre with you and point them in the right direction :-) they may open the phone up for you and have a look so your warranty remains intact