Did you try 465 as well? Try some of the other ports. Is it possible your ISP is filtering port 25?
I just tried telnet on that host you posted and it works fine for me.
Last login: Fri Feb 8 11:31:10 on console
Frosts-Mac-Pro:~ fr0stspire$ telnet
(to) gmail-smtp-in.l.google.com 25
Connected to gmail-smtp-in.l.google.com.
Escape character is '^]'.
220 mx.google.com ESMTP f9si43998037paw.256 - gsmtp
250-mx.google.com at your service, [126.96.36.199]
If you have a firewall switch it off just for testing purposes. Try using telnet from a different host on your network. Seems like the issue is confined to your end. If you are on a DHCP assigned IP for your internet router, see if you can pick up a new ip by going to your mac address clone in your router, pick "use this mac address option" take any two or more numbers or letters and change them. hit save. Power cycle your router and you shall now have a new IP. Test again.
FYI if you are on a DHCP assigned IP on the host you are testing from, you will automatically be blacklisted since DHCP assigned blocks are almost always on blacklists by default. And you cannot be removed from a blacklisted IP block as your ISP is the one who put it there to begin with in most cases. They are trying to stop spam from all angles these days.