ANTES DE FAZER QUALQUER COISA: Eu recomendo strongmente que você use um usb ao vivo para tentar recuperar seus dados. Não inicialize o Ubuntu a partir do disco rígido, ou estará em risco de sobrescrever permanentemente os dados perdidos no disco rígido.
Veja a ferramenta photorec.
Para instalá-lo:
$ sudo apt-get install testdisk
Isso instalará o testdisk e seu subcomponente photorec. O testdisk é mais poderoso, mas pode fazer com que você perca dados, portanto use o photorec primeiro. photorec só lê dados, por isso é seguro usar (By the way, você pode usar photorec como um usuário quando você deve ser root para usar testdisk).
$ photorec
$ sudo testdisk # Use that one as a second choice.
É um software de console, espero que você não tenha medo :-D.