После того, как Вы прописали новые NS Вашего домена, должно пройти время обновления зон ДНС у Вашего провайдера (от 4 до 72 часов). За это время информация о домене будет обновлена на других серверах сети.
Если ваш старый провайдер закрыл Ваш хостинг аккаунт, а домен еще не проделегировался полностью — он может быть временно невидим для каких-то зон.
Не обязательно для всех — даже в пределах одного города возможны варианты!