Все, что ниже спутников- является помехами

1) Софт. Переустановить Навител, поюзать прогу GPS-Test ( вроде так),- показывает реальную чувствительность приемника.
2) Антена. Физические проблемы. Если тел падал,- возможно отвалился контакт, типа "есть контакт, нет контакт"...
Почитай на 4Pda о своем телефоне, возможно найдешь что-нить полезное. Как,например, здесь : GPS - модернизация антенны.