С МТС запустился без проблем. В итоге отправил сообщение с настройками Билайна на номер МТС, потом вставил симку Билайна и заработало.
Почему до этого настройки не применялись - непонятно. В этот раз сообщение с настройками отправлял с другого телефона.