Есть у меня предположение, что у этого телефона может быть проблема именно с работой в диапазоне 1800 MHz.
Дело в том, что у всех перечисленных операторов абсолютно одинаков принцип регистрации терминала в сети: вначале он пытается зарегистрироваться в диапазоне 1800 MHz, и только если это сделать не удалось, пытается сделать то же самое уже в диапазоне 900 MHz.

Так что можешь рыть в этом направлении, это не исключено - я видел не раз подобные проблемы с разными моделями телефонов, где причинами были именно неисправности, которые не давали нормально работать в диапазоне 1800.

Было бы неплохо проверить это тело в сети UMC где-нибудь за пределами города, где есть только покрытие 900 MHz.

Кроме того, можно активировать в телефоне Net Monitor и кое-что поанализировать.