Кратко докладываю о результате:
1. Через телефон Samsung GT-C3530 к интернету не удалось подключиться ни разу. Есть мысль о несовместимости телефона и навигатора (м.б. версии БТ разные).
2. Все Nokia (E65, C5-00, ExpMus) заработали как с МТС, так и с Мегафон. Причем ничего интелектуального не делалось, просто длительный процесс вкл/выкл сервисов в навигаторе в разном порядке. В сервисе подсказали отключить в телефоне запрос PIN кода - никак не повлияло. Единственное, что можно отметить - с МТС получалось быстрее, чем с Мегафон, но это скорее статистика, чем закономерность.
Вывод - видимо,