Relay Access Denied – Postfix – Ubuntu

Been having a bit of trouble getting my Ubuntu server to relay my mail to external addresses. Here's whats currently happening:

When I telnet locally to port 25 I can send email to any host just fine. However, when I try to connect from my Mac here to the server, I get a Relay Access Denied error after I enter the rcpt to: section of the message body.

So, my question is – why is this happening? How can I fix it? I'd ideally like to make it so any mail client anywhere can connect to a mailbox on my server (clients, etc.)

Here's my /etc/postfix/main.cf file:

# See /usr/share/postfix/main.cf.dist for a commented, more complete version


# Debian specific:  Specifying a file name will cause the first
# line of that file to be used as the name.  The Debian default
# is /etc/mailname.
#myorigin = /etc/mailname

smtpd_banner = $myhostname ESMTP $mail_name (Ubuntu)
biff = no

# appending .domain is the MUA's job.
append_dot_mydomain = no

# Uncomment the next line to generate "delayed mail" warnings
#delay_warning_time = 4h

readme_directory = no

# TLS parameters
smtpd_tls_cert_file=/etc/ssl/certs/ssl-cert-snakeoil.pem
smtpd_tls_key_file=/etc/ssl/private/ssl-cert-snakeoil.key
smtpd_use_tls=yes
smtpd_tls_session_cache_database = btree:${data_directory}/smtpd_scache
smtp_tls_session_cache_database = btree:${data_directory}/smtp_scache

# See /usr/share/doc/postfix/TLS_README.gz in the postfix-doc package for
# information on enabling SSL in the smtp client.

myhostname = sites.domain.co.uk
alias_maps = hash:/etc/aliases
alias_database = hash:/etc/aliases
myorigin = /etc/mailname
mydestination = sites.domain.co.uk, localhost.domain.co.uk, , localhost
relayhost = 
mynetworks = 127.0.0.0/8 [::ffff:127.0.0.0]/104 [::1]/128 <my_ip_address>
mailbox_size_limit = 0
recipient_delimiter = +
inet_interfaces = all

smtpd_client_restrictions = reject_rbl_client sbl.spamhaus.org, reject_rbl_client blackholes.easynet.nl, permit

Output of my Telnet session on the server:

root@sites:~# netcat localhost 25
220 <my_hostname> ESMTP Postfix (Ubuntu)
ehlo <some_host>
250-<my_hostname>
250-PIPELINING
250-SIZE 10240000
250-VRFY
250-ETRN
250-STARTTLS
250-ENHANCEDSTATUSCODES
250-8BITMIME
250 DSN
mail from: <my_email>
250 2.1.0 Ok
rcpt to:<email>@googlemail.com
250 2.1.5 Ok
data
354 End data with <CR><LF>.<CR><LF>
test
.
250 2.0.0 Ok: queued as D5710120773
quit
221 2.0.0 Bye
root@sites:~# 

And the result when I try to telnet from my Mac:

iMac:~ user$ telnet <my_hostname> 25
Trying 146.185.151.96...
Connected to <my_hostname>.
Escape character is '^]'.
220 <my_hostname> ESMTP Postfix (Ubuntu)
ehlo <some_host>
250-<my_hostname>
250-PIPELINING
250-SIZE 10240000
250-VRFY
250-ETRN
250-STARTTLS
250-ENHANCEDSTATUSCODES
250-8BITMIME
250 DSN
mail from: <my_email>
250 2.1.0 Ok
rcpt to: <email>@googlemail.com
554 5.7.1 <<email>@googlemail.com>: Relay access denied

I've searched the site and tried various suggestions but none seem to be working for me! Any help would be greatly appreciated.