Linux – Postfix: Can’t receive mail from outside the box

I've followed this tutorial in order to get a postfix mail server with virtual domains running:

http://flurdy.com/docs/postfix/

Right now I still have not implemented the whole tutorial but I have stopped after here:

http://flurdy.com/docs/postfix/#config-simple-imap

Right now I would like to be able to send emails, which I'm able to do, and also receive emails from the world. Right now when I send an email from me@gmail.com I get it rejected by postfix:

Sep 16 09:24:04 myhost postfix/smtpd[25086]: connect from mail-vw0-f44.google.com[209.85.212.44]
Sep 16 09:24:04 myhost postfix/smtpd[25086]: NOQUEUE: reject: RCPT from mail-vw0-f44.google.com[209.85.212.44]: 554 5.7.1 <root@example.com>: Relay access denied; from=<me@gmail.com> to=<root@example.com> proto=ESMTP helo=<mail-vw0-f44.google.com>
Sep 16 09:24:05 myhost postfix/smtpd[25086]: disconnect from mail-vw0-f44.google.com[209.85.212.44]

I must say I'm able to telnet example.com 25 even from outside and from the localhost without problems.

If I send a mail from localhost by running echo .This will go into the body of the mail.. | mail -s -v .Hello root@example.com I'm getting the following error where x.y.w.z symbolizes my public ip address so there's no mail to check for root user:

Sep 16 09:28:55 myhost postfix/cleanup[25097]: 92E4124E11: message-id=<20110916092855.92E4124E11@mail.example.com>
Sep 16 09:28:55 myhost postfix/qmgr[17100]: 92E4124E11: from=<>, size=2566, nrcpt=1 (queue active)
Sep 16 09:28:55 myhost postfix/bounce[25106]: 5E25724E10: sender non-delivery notification: 92E4124E11
Sep 16 09:28:55 myhost postfix/qmgr[17100]: 5E25724E10: removed
Sep 16 09:28:55 myhost postfix/smtpd[25104]: connect from example.com[x.y.w.z]
Sep 16 09:28:55 myhost postfix/smtp[25103]: warning: host mail.example.com[x.y.w.z]:25 greeted me with my own hostname mail.example.com
Sep 16 09:28:55 myhost postfix/smtp[25103]: warning: host mail.example.com[x.y.w.z]:25 replied to HELO/EHLO with my own hostname mail.example.com
Sep 16 09:28:55 myhost postfix/smtp[25103]: 92E4124E11: to=<ec2-user@example.com>, relay=mail.example.com[x.y.w.z]:25, delay=0.01, delays=0.01/0/0/0, dsn=5.4.6, status=bounced (mail for example.com loops back to myself)
Sep 16 09:28:55 myhost postfix/smtpd[25104]: disconnect from example.com[x.y.w.z]
Sep 16 09:28:55 myhost postfix/qmgr[17100]: 92E4124E11: removed

Here goes a part of /etc/sysconfig/network i think the problem could be mynetworks_style value??:

myhostname = mail.example.com
mydomain = example.com
myorigin = example.com

relayhost =
inet_interfaces = all
mynetworks_style = host

cat /etc/mailname

mail.example.com

Here is my /etc/hosts file, the real hostname is myhost.example.com but as GoDaddy zone file has an MX entry called mail.example.com which points x.y.w.z as well as example.com does, I added the mail.example.com alias also here because in postfix configuration file I use the name mail.example.com while Apache uses example.com

cat /etc/hosts:

127.0.0.1       myhost.example.com localhost localhost.localdomain mail.example.com
#public ip address
x.y.w.z    example.com www.example.com mail.example.com
#private ip address
a.b.c.d  myhost.example.com mail.example.com www.example.com example.com