Quando você desinstalou, você removeu sua pasta .steam em seu diretório pessoal?
Observe que, antes de fazer isso, você deve fazer backup dos arquivos do jogo para não precisar baixar todos os seus jogos novamente.
Se você não fez isso, é provável que alguma configuração tenha sido danificada em sua pasta pessoal e não tenha sido removida quando você a desinstalou.
Só para acrescentar que atualizei de 12,10 para 13,04 sem problemas e o Steam funciona perfeitamente, então deve funcionar assim que você limpar os arquivos antigos.