Ping working seems to indicate you have a route to internet. If you are using the ping to your VPS using its IP and ssh with the hostname is not working, try using ssh with the IP too because it may be a DNS issue.
If ping is working with the public hostname of your VPS, ssh should work the same unless there is something (firewall or proxy) blocking outgoing connections on port 22 or there is a proxy in the LAN not configured to proxy port 22 transparently (only 80 probably). If this is the case, you may be able to use ssh defining the proxy settings for the ssh connection (if the server allows it) but without knowing more it is not easy to indicate a real solution if any.
EDIT after comments:
Seeing telnet on port 80 works and not on port 22, outgoing is probably blocked on port 22 (assuming your VPS ssh server is working and listening!). I think you have a few options:
- talk to the admin of your Provider and see what he can do to open port 22
- change the port your VPS ssh server is listening to a non blocked port
- use the console of your VPS if available. Usually this is accessed from the website and with a java or ajax connecting console directly to your server.
Anyways, you'll have to connect using the 3rd option to be able to change the listening port for option 2 unless you can have your VPS provider to do this for you.