Cyberbabe

gps по техническим причинам не может выдавать ответ моментально, ей нужен 'прогрев', предварительный сбор данных и везение, т.е. наличие спутников в видимости и отсутствие помех от переотражений (здания).

Запусти приложение android gps test и посмотри визуально как у тебя это происходит, как идет сбор информации о спутниках.

Проверь, включена ли поддержка a-gps и есть ли интернет, это должно заметно ускорить получение координат.
из вики:

Некоторые приёмники с A-GPS объединены с радиомодулем (GSM) и не могут стартовать, если радиомодуль отключен.

p.s. укажи вместо gps - network, координаты будут определены моментально по сетям мобильного провайдера, с большой погрешностью до сотен метров но надо ли тебе точнее?

Относительно быстрый (до 90 секунд) старт устройства GPS возможен только при условии предоставления данных A-GPS (assisted GPS) по альманаху и эфемеридам. Обычно A-GPS предоставляет сотовый оператор. Если сотовой связи нет (отключена), или устройство было выключено на длительный срок, или было перемещено в отключённом состоянии на значительное расстояние, то производится "холодный старт", это значит, эфемериды (а в отдельных случаях и альманах) будут обновляться по данным со спутников и процедура эта может занимать до 30 минут.