Thanks for the suggestions all.

I've been driving in nice open spaces, I don't live or work in the city. I have my device mounted on the dash and it can see the sky.

I've tried switching to the Google server, although the Nokia server has better pings where I am. That didn't make a difference.

That's interesting @somedude re the bluetooth connection, I have it permanently connected when I'm in the car. I might turn that off tomorrow and have a go.

Just out of interest, I might try disabling the A-GPS. I'm travelling overseas in a few weeks and I won't be using the A-GPS to avoid roaming costs.