Linux – Ubuntu Linux – Postfix is rejecting all email coming from non-localhost

I am not sure exactly what is going wrong here, but my server (Postfix?) seems to be rejecting all external emails going to the server example.info.

Here is the bounce-back message I am receving, similar with Gmail and Yahoo.

Delivery to the following recipient failed permanently:

    me@example.info

Technical details of permanent failure:
Google tried to deliver your message, but it was rejected by the recipient domain. We recommend contacting the other email provider for further information about the cause of this error. The error that the other server returned was: 550 550 #5.1.0 Address rejected me@example.info (state 14).

----- Original message -----

MIME-Version: 1.0
Received: by 10.216.138.89 with SMTP id z67mr2663854wei.10.1329000093343; Sat,
 11 Feb 2012 14:41:33 -0800 (PST)
Received: by 10.180.95.195 with HTTP; Sat, 11 Feb 2012 14:41:33 -0800 (PST)
Date: Sat, 11 Feb 2012 15:41:33 -0700
Message-ID: <CAJ=woPqVkUYs7_4YicV62Vvt4hQ7eHqcorxSgC3dcOsUCwd05Q@mail.gmail.com>
Subject: test
From: My Name <me@gmail.com>
To: My Name <me@example.info>
Content-Type: text/plain; charset=ISO-8859-1

test

I am not really an expert at this email thing; I was just tasked with it because I am the database architect at work. Apparently I have assumed the role of ALL IT management/support.

I have registered my domain at Godaddy, however, the only thing it does is point to a box stored inside the server room in my office; Godaddy isn't hosting anything.

Do I have some kind of MX registration problem? What kind of logs would be helpful for debugging this kind of issue?

I will post a photo of my MX records at Godaddy here:

PS: On the plus side; I can send mail via command prompt and all servers are accepting them as non-spam.

Edit: Output of postconf -n

alias_database = hash:/etc/aliases
alias_maps = hash:/etc/aliases
append_dot_mydomain = no
biff = no
broken_sasl_auth_clients = yes
config_directory = /etc/postfix
home_mailbox = Maildir/
inet_interfaces = all
inet_protocols = all
mailbox_command =
mailbox_size_limit = 0
mydestination = localhost, localhost.localdomain, example.com
myhostname = example.com
mynetworks = 127.0.0.0/8
myorigin = /etc/mailname
readme_directory = no
recipient_delimiter = +
relayhost =
smtp_tls_note_starttls_offer = yes
smtp_tls_security_level = may
smtp_tls_session_cache_database = btree:${data_directory}/smtp_scache
smtpd_banner = $myhostname ESMTP $mail_name (Ubuntu)
smtpd_recipient_restrictions = permit_sasl_authenticated,permit_mynetworks,reject_unauth_destination
smtpd_sasl_auth_enable = yes
smtpd_sasl_local_domain =
smtpd_sasl_security_options = noanonymous
smtpd_tls_CAfile = /etc/ssl/certs/cacert.pem
smtpd_tls_auth_only = no
smtpd_tls_cert_file = /etc/ssl/certs/smtpd.crt
smtpd_tls_key_file = /etc/ssl/private/smtpd.key
smtpd_tls_loglevel = 1
smtpd_tls_received_header = yes
smtpd_tls_security_level = may
smtpd_tls_session_cache_database = btree:${data_directory}/smtpd_scache
smtpd_tls_session_cache_timeout = 3600s
smtpd_use_tls = yes
tls_random_source = dev:/dev/urandom
virtual_alias_domains = example.com
virtual_alias_maps = hash:/etc/postfix/virtual