They can have a ton or reasons for blocking connections.
Have you asked them if there is anything they do to block outgoing connections?
A simple way to check it is by doing what you are doing now: try to connect, and if it works it works.
You may want to give it a try with fsockopen, because that will just try to connect on a socket level. mysql_connect() can also fail because of bad username/password/host etc.