gps по техническим причинам не может выдавать ответ моментально, ей нужен 'прогрев', предварительный сбор данных и везение, т.е. наличие спутников в видимости и отсутствие помех от переотражений (здания).
Запусти приложение
android gps test и посмотри визуально как у тебя это происходит, как идет сбор информации о спутниках.
Проверь, включена ли поддержка a-gps и есть ли интернет, это должно заметно ускорить получение координат.
из вики:
Некоторые приёмники с A-GPS объединены с радиомодулем (GSM) и не могут стартовать, если радиомодуль отключен.
p.s. укажи вместо gps - network, координаты будут определены моментально по сетям мобильного провайдера, с большой погрешностью до сотен метров но надо ли тебе точнее?
