Vad jag vet görs DNS-förändringar av NIC-SE. De kräver bland annat att de nya DNS-servrarna svarar korrekt för domänen innan DNS-bytet sker, vilket kan leda till lite problem om webbhotellet inte lägger till domänen i DNS-en förrän rätt servrar angetts ;-)
http://www.nic-se.se/domaner/ompekning.shtml
Men det du kanske kan göra är att använda dig av någon DNS-tjänst som inte är knuten till ett specifikt webbhotell. När du byter webbhotell så ändrar du bara IP i inställningarna för DNS:en.