Lync 2010 Endpoint was unable to register

So after deploying a Standard edition of Lync 2010, When testing the outside connectivity I'm getting an error: The endpoint was unable to register.

I make sure everythins was properly in place: DNS entries on external DNS and open ports on the outside firewall.

Here's the output:

Test Steps
Testing remote connectivity for user lync2010@lync.mydomain.com to the Microsoft Lync server.
Specified remote connectivity test(s) to Microsoft Lync server failed. See details below for specific failure reasons.
 Tell me more about this issue and how to resolve it

Additional Details
Couldn't sign in. Error: Error Message: The endpoint was unable to register. See the ErrorCode for specific reason.

Error Type: RegisterException.
Deregister Reason: None.
Response Code: 504.
Response Text: Server time-out.

I have ran a portscan on a box I have on the public Internet and all ports are actually open:

[ec2-user@ip-xx-xxx-xxx-xx ~]$ nmap xx.28.99.xx

Starting Nmap 5.51 ( http://nmap.org ) at 2013-07-01 13:30 EDT
Nmap scan report for www.mydomain.com (xx.28.99.xx)
Host is up (0.020s latency).
Not shown: 997 filtered ports
PORT STATE SERVICE

443/tcp open https

444/tcp open snpp

5061/tcp open sip-tls

The public IP on this server is NATted through a Firewall, so my external config will look something like this:

SIP Access:
lync.mydomain.com
Port: 5061
Protocol: TLS

SIP Access:
lync.mydomain.com
Port: 444
Protocol: TLS

SIP Access:
lync.mydomain.com
Port: 443
Protocol: TCP

Both servers are reacheable within each other, Front-End and Edge. I can't seem to find any solution to this.