Whenever any user tries to connect to my server it gives them the error "Authentication servers are down. Please try again later, sorry!"
[14:36:54] User Authenticator #5/ERROR: Couldn't verify username because servers are unavailable
[14:36:54] [Server thread/INFO]: com.mojang.authlib.GameProfile@476cab2e[id=<null>,name=tortib,properties={},legacy=false] (/xx.xxx.xx.xx:51072) lost connection: Authentication servers are down. Please try again later, sorry!

I have OUTPUT rules set in my iptables:
0 0 ACCEPT tcp – * * 0.0.0.0/0 23.23.94.140 tcp
0 0 ACCEPT udp – * * 0.0.0.0/0 54.243.65.91 udp

Whenever someone tries to connect to the server the packets (first zero) and bytes (second zero) does not increment at all. This indicates that java is not even trying to make a connection to the auth servers. When I run curl https://authserver.mojang.com I receive the following output:

{"Status":"OK","Runtime-Mode":"productionMode","Application-Author":"Mojang Web Force","Application-Description":"Mojang Authentication Server.","Specification-Version":"2.5.13","Application-Name":"yggdrasil.auth.restlet.server","Implementation-Version":"2.5.13_build250","Application-Owner":"Mojang"}

Iptables rule is appearing to hit the packets:
pkts bytes target prot opt in out source destination
10 934 ACCEPT tcp – * * 0.0.0.0/0 23.23.94.140 tcp

So the server is being reached.

This problem started to occur when 1.8 was released, I was running 1.7.10 at the time and I was receiving the auth error. I updated to 1.8 server & client and I'm still receive the exact same error. I have tried to remove jre and reinstall it, I have put the minecraft_1.8.jar server in another dir and ran it to start a fresh install and that didn't help either. I'm seriously at my wits end. My server hostname is tortibshells.com.