Такая же проблема была. Samsung Galaxy S, версия ПО Navitel 5.0.0.778. Обновил с сайта на Navitel 5.0.0.1069 и всё стало норм. Только при первом входе в прогу попросил соединение с инетом, чтобы обновить лицензию с "Регион+" на «Федеральный Округ». P.S. Поиск по адресу работает норм