You'll need to log into the console when you can't access the OS normally. That allows you to see why the server is hanging on (re-) boot, resolve networking and firewall issues etc.
Typically enterprise class server hardware comes with provisions for out of band management, either based on the open IPMI standard or the more proprietary options such as HP's ILO, Dell's DRAC, Oracle/SUN ILOM, which allows you to access the console even though the OS (your SSH session) is not available.
Many VPS providers also allow you access to the console through their server management panel.
Sometimes waiting is sufficient, some processes may take a fair bit of time to shut correctly and some hardware takes a long time to pass the POST stage and if you have a large amount of storage undergoing a manadatory fsck that too can take some time.
Since you mention Hetzner in your comments: http://wiki.hetzner.de/index.php/LARA/en
Operation timed out
usually points to a firewall problem. If the sshd wouldn't be running your ssh client would give a different error (connection refused
or something like that). Log on to your server locally and check the firewall settings to allow incoming SSH connections.