Anyway, this is a common problem (and one I've fixed on my own many many times).
Since you used two different computers to try to connect, I'll assume those are fine.
What this problem means, is that your Minecraft server cannot connect to the Mojang Username Authentication servers.
Now, many things could cause that, these are some of the common ones (shut down the MC server first):
1: Obviously, check to make sure your server has a complete, working connection to the internet.
2: Check the hardware AND system time on your Linux server, make sure they are at least within the same minute as realtime. If not, set them both to realtime (this also includes the day, month, and year).
If 2 solved your problem, check the CMOS battery (little watch battery) on your motherboard, it's probably dead. Not a big problem, just an inconvenience, as the time will be off every time the server does not have power.
Try 1 and 2, and see if that fixes it. Those are the easiest solutions, and generally the cause of the problem.
Rollback Post to RevisionRollBack
Want to host a dedicated server yourself, easily, and for free? Click here!
So it turns out the issue was specific to my server (likely...I doubt anyone will encounter this issue) but the problem was after my server rebooted early this morning from a crash. After the reboot CPanel reset some of my network settings to what they were at my hosts previous datacenter, oddly while i could log into the server and hit my website, it was unable to talk to authentication servers.