I can send/rec mail fine, but as soon as i try to mail to a gmail address it dont get to where i sent it, i checked the WHM Mail Queue and got this:

156P Received: from mailnull by cpanel.liquidexploit.com with local (Exim 4.50)
id 1DvEbc-000732-HS
for xxxxx@gmail.com; Wed, 20 Jul 2005 23:27:24 +1000
043 X-Failed-Recipients: xxxxx@gmail.com
031 Auto-Submitted: auto-generated
068F From: Mail Delivery System
026T To: xxxxx@gmail.com
059 Subject: Mail delivery failed: returning message to sender

with the message, so it didnt even get back to me!

Check the rest of the failure message or your logs to see why it's not being delivered.

try from ssh to ping gmail.com

and see if you get any ip, just to see if it could be a dns problem.