yugaee:
Probablemente este nuevo servidor de correo requiere de autenticacion por lo que tu problema se solucionara con la clase phpmailer o similares.
Ellos en la configuracion de sus servidores de correo tienen la potestad de NO requerir autenticacion y ellos pueden permitir lo que se llama "Relay" de tu IP y asi pasa el correo con la funcion mail sin problema.
Habla con ellos y solicitales que tu IP no requiera autenticacion en el servidor de correo de ellos y si no quieren o no entienden pues adquire esta clase de que te mencione arriba.
Saludos
Franco
P.S. Es medular que les menciones que con tu anterior proveedor las cosas caminaban bien y presionalos por un "Relay" y lo lograras.