In most cases gmail is rejecting mail is because bad email configuration or dns configuration.
Post the output of following commands:
hostname
hostname -f
cat /etc/mailname
You can try to check if your IP or MX is open relay:
http://www.spamhelp.org/shopenrelay/