The answer is: ask your provider / sysadmin to change the DNS primary master IP to listen the new server.
Apparently a DNS listens to a certain IP for DNS changes. In the specific case that you move your server (1 vps to other vps with different IP) the DNS server is listening for DNS changes on the old IP. It neglects the new DNS settings from the server on the new IP.
When the sysadmin has changed the master IP in DNS to listen to the new server, then the new DNS settings and new domain will be found.
I hope this helps you out - this took me quite while to figure out