bueno primero que nada te sugiero usar esta herramienta
www.intodns.com con la que veras si esta bien configurado tu DNS si hay algun error te lo mostrara, segun dices, yo pienso que el problema son tus zonas DNS, como usas los mismos nameserver, seguro en en tu zona DNS de tus dominios en tu nuevo VPS aun existen rastros de las anteriores IP's y tengas que cambiarlas manualmente, ayudaria saber si manejas algun panel de control, para indicarte donde puedes solucionarlo, saludos