[Oleg Krylov]

хотелось бы узнать как это сделать? платная ли это услуга у большинства провайдеров? »

Вы меняете провайдера, а не PrimaryNS. Так что это зависит скорее не от провайдера...
Наберите:
nslookup
set type=mx
<Имя Вашего домена>
Вывод должен быть вида:
Non-authoritative answer:
webzavod.ru MX preference = 5, mail exchanger = sledge.samara.net - это и есть МХ-запись

webzavod.ru nameserver = ns.mustdie.ru - это серверы где она хранится
webzavod.ru nameserver = ns.webzavod.ru
sledge.samara.net internet address = 195.128.128.21

Вот там ее и нужно править. Обычно услуга бесплатна.
По поводу коннекта - смотрите SMTP-лог на предмет отправки.