O ping funcionando parece indicar que você tem um caminho para a internet. Se você estiver usando o ping para o seu VPS usando seu IP e ssh com o nome do host não está funcionando, tente usar o ssh com o IP também, porque pode ser um problema de DNS.
Se o ping estiver trabalhando com o nome de host público do seu VPS, ssh deve funcionar da mesma maneira, a menos que haja algo (firewall ou proxy) bloqueando conexões de saída na porta 22 ou haja um proxy na LAN não configurado para a porta proxy 22 de forma transparente (apenas 80 provavelmente). Se este for o caso, você poderá usar o ssh definindo as configurações de proxy para a conexão ssh (se o servidor permitir), mas sem saber mais, não é fácil indicar uma solução real, se houver.
EDIT depois dos comentários:
Ver o telnet na porta 80 funciona e não na porta 22, provavelmente a saída está bloqueada na porta 22 (supondo que o servidor ssh do seu VPS esteja funcionando e ouvindo!). Eu acho que você tem algumas opções:
- fale com o administrador do seu provedor e veja o que ele pode fazer para abrir a porta 22
- altere a porta que seu servidor ssh do VPS está escutando para uma porta não bloqueada
- use o console do seu VPS, se disponível. Normalmente, isso é acessado a partir do site e com um console de conexão java ou ajax diretamente para o seu servidor.
De qualquer forma, você terá que se conectar usando a 3ª opção para poder alterar a porta de escuta para a opção 2, a menos que você possa ter seu provedor de VPS para fazer isso por você.