SSH Timed Out (Post-update/upgrade/reboot)

After an update and upgrade followed by a reboot I am unable to access my server via SSH. I was able to boot into rescue mode and also use a KVM to identify some problems at boot, but fixed them all. Now everything is booting up seamlessly and working fine when I’m either (1) in rescue mode or (2) logged into the server in regular mode via the KVM.

When I’m in rescue mode I can ping the server and get a good traceroute from my home computer terminal. As soon as I reboot into regular mode I get an “Operation timed out” when I try to login via SSH (Something that was working just fine prior to the update/upgrade and reboot) and ping gives me a “Request timeout for imp_seq” countdown and traceroute gets held up at the step when it reaches my server host’s domain name.

The server support people think it’s a firewall issue but the firewall, as far as I know, is disabled (Not sure why that would’ve changed with an update/upgrade and reboot). I’m really at a loss.

I’ve already tried this (Solution to: inaccessible server and ping down after installing quickbox on some Online & OneProvider servers) as a hail mary, but I don’t even have that PCI so I’m not surprised it didn’t work.

Any help is appreciated.