Eu tive o mesmo problema há duas semanas e usei diskinternals linux recovery no windows para escanear minha partição linux e recuperar alguns dos meus arquivos. Não consegui recuperá-los, mas fiquei feliz por ter funcionado até certo ponto.
Sua pasta de início não foi realmente excluída, acabou de ser movida. Eu me deparei com o meu uma semana depois que eu atualizei de 11,10 para 12,04LTS e menino eu estava feliz. Siga as instruções abaixo.
Abra sua pasta pessoal e selecione o ícone do sistema de arquivos sob o ícone de vídeo no lado esquerdo da tela. Abra a pasta inicial e selecione o ícone da sua antiga conta de usuário. É isso aí. Você deve ter todos os seus arquivos anteriores organizados em suas pastas.
Deixe-me saber se isso resolve o seu problema (isto é, se você ainda não fez isso).