I have the same issue, but its because I have put my phone in my pocket. It needs to be able to "see" the satellite otherwise it can't accurately fix your position.
If you are driving put it on the dash board. If cycling or walking maybe putting it around your neck or inside your pocket if you have thin material trousers and no long coat on.
I don't know though, just suggestions.