По станадрту NMEA время холодного старта GPS до 12 (или 15, точно не помню) минут, которые минимально необходимы чтобы получить от спутников альмонах и эфимериды (если они у вас уже есть от предыдущего старта или скачаные с интернета, то старт будет быстрее, в зависимости от их актуальности). После чего собственно уже работает банальный прием "кординат".
По поводу хождения по комнате вы учитывайте несколько моментов:
1. В помещении GPS обычно не ловит, в лучшем случае видно несколько спутников (а для хоть какого-нибудь позиционирования в трехмерном пространстве нужно минимум 4 спутника), и это основная причина в вашем случае.
2. Даже если спутники видны, нужно время на получение информации базовой информации для вычислений (вышеназванные эфимериды и альмонах). И чем реже вы включаете GPS, тем дольше будет старт, по причине устаревания вышеназванной информации.
Поповоду переинициализации - выключение питания телефона.
А вообще, в NMEA (и, уверен, что в андроидовском API тоже) есть признак достоверности кординат, который следует проверять.