I am able to connect to this database anywhere it seems, except for my actual host! (current)

This is the error I receive (after a 1-2 min lag):

Warning: mysql_connect(): Can't connect to MySQL server on '[new_server_ip]' (4) in /test.php line 2
I cannot connect to the database because: Can't connect to MySQL server on '[new_server_ip]' (4)

I have spoken to my new host about this and they have confirmed all of the settings are in place to allow me to remotely connect. And as I've said, I could easily connect via my localhost on my PC even.

Is this a server issue, or simply just a host issue?

I realize I am not supposed to name-drop here, but I feel that if the problem lies within the host's settings, someone reading this may know better than I.

Current host: Goddaddy (whom I'm moving from)