VPS host can't send email to Google and Yahoo Mail

Hi, I got a new VPS setup and I'm wondering why I can't send emails to yahoo and gmail. Here's the error in /var/log/maillog:

00:43:00 mylamp sendmail[32507]: o45Gh0nc032505: to=, ctladdr= (48/48), delay=00:00:00, xdelay=00:00:00, mailer=esmtp, pri=120405, relay=alt4.gmail-smtp-in.l.google.com. [74.125.79.27], dsn=4.0.0, stat=Deferred: Connection refused by alt4.gmail-smtp-in.l.google.com

What seems to be the problem?

From serverfault mandeler

• Could be your IP got black-listed by a previous owner of your VPS's IP. Common for an un-managed VPS to be compromised by a spammer or other blackhat activity in the wild.

  Edit: Also, make sure your reverse DNS (rDNS) is set up properly, as big SMTP servers will need this to verify you are who you say you are.

  TomTom : THat pretty much sums it up. Use something like http://www.mxtoolbox.com/blacklists.aspx to check whether your server is OK or the IP is burned ;)
  From mtkoan

• We would agree with mtkoan and TomTom...verify that you are not:

  Blacklisted, have correct MX Records and rDNS and lastly, you can use our site to run SMTP Diagnostics which heck for Open Relay, HELO response and more.

  http://mxtoolbox.com

  Let us know if you have any other additional issues or questions.

  Thank you,

  @MxToolBox

  From MxToolBox Support