REVISÃO COMPLETA:
Eu sugeri usar o RIP Linux porque esqueci o nome da ferramenta real incluído nele que eu usei. Eu verifiquei, e acontece que a ferramenta é chamada PhotoRec. Como eu disse, ele varre uma partição procurando por padrões que lembram certos tipos de arquivos, depois os copia para um local diferente.
Acontece que o PhotoRec está realmente disponível a partir do repositório do APT do Ubuntu, então se você atualmente tem o Ubuntu instalado e rodando, ou você já está rodando ao vivo, então você pode instalar o PhotoRec e executá-lo no Ubuntu. Isso pode ser mais conveniente.
Além disso, descobri que o PhotoRec tem um parente que pode ser mais útil nessa situação: TestDisk. O TestDisk pode executar outras operações, incluindo, mas não se limitando a, restaurar tabelas de partição. Se você não fez nenhuma alteração importante no disco desde a exclusão da partição, isso pode permitir que você restaure a partição e a maioria dos arquivos nela para que você possa acessar a maioria dos arquivos antigos acessando Meu computador. Note que você provavelmente não conseguirá inicializar a partição depois de restaurá-la, e provavelmente perderá todas as novas partições.
As duas ferramentas podem ser encontradas aqui: link