Urgent server not delivering emails

[s_2_s]

Hello
i just rented a new server and its not delivering emails at all
i tried to send an email to a gmail email
and it traced this in the exim_mainlog

2007-11-02 01:28:43 1InjMh-00046K-OF gmail.com [64.233.161.83] Connection timed out
2007-11-02 01:29:10 1InitW-0003sA-S7 gmail.com [64.233.171.83] Connection timed out
2007-11-02 01:29:33 1InjGr-0003zL-Ju gmail.com [72.14.253.83] Connection timed out
2007-11-02 01:29:33 1InjGr-0003zL-Ju == XXXXXXXXXX@gmail.com R=lookuphost T=remote_smtp defer (110): Connection timed out


the same thing happends for hotmail , yahoo and any other email even those non free emails ex user@domain.com

please HELP

[sarhosting]

Does the message delay or bounce back, can you provide a bounce back message and or a delay message - if not then I would speak to the providers of your connectivity. Thats the best bet!