Well,
it's hard to say what can be the problem...
Can you test the other server? For instance gmail, or something? It may be some issue related to the PHP code and then probably it shouldn't work for any server.
If it'll work for the other server, then maybe you should try some other configuration for your server.
In fact the best way to solve this issue is the hardest - debug connection errors.
Regards,
Adam