Recuperar nunca é um processo fácil e deve ser feito sempre com a noção que provavelmente perdeu tudo. O que recuperar já vai ser bom. Ou seja, dificilmente consegue recuperar tudo.
Bom, quando se formata, basicamente os dados ficam todos na mesma no disco, o que acontece é que a tabela que apontava para a localização dos ficheiros é apagada e então você não tem acesso aos ficheiros pois não tem o "caminho" para lá chegar. Ora, esse ficheiros mantêm-se lá até você escrever algo por cima. Por isso se instalou o ubuntu provavelmente já houve muitos ficheiros sobrepostos.
Assim, a minha recomendação principal é: se quer recuperar uso o mínimo possível do computador até iniciar a recuperação. Quanto a realizar a recuperação, eu não sou a pessoa indicada para sugerir aplicações pois infelizmente (ou felizmente) só usei uma vez um programa e... fui muito pouco bem sucedido visto que estava a tentar recuperar algo que tinha apagado semanas antes, onde a probabilidade de ter sido escrito por cima era grande.
Existe vários programas que você pode encontrar no link abaixo. Basicamente esses programas procuram pelo disco por possíveis ficheiros através de padrões comuns que determinados formatos de ficheiros têm no seu cabeçalho (início do ficheiro). Por isso, tente correr os programas a ver se consegue recuperar:
Se os dados forem mesmo importantes para si, pode sempre seguir uma das dicas que se costuma recomendar (e que tem no link acima): faça uma cópia exata do disco e tente recuperar nessa cópia. Faça vários testes de recuperação. Assim a qualquer momento pode voltar a fazer outra cópia e tentar outra vez recuperar, mantendo a salvo os dados soltos do disco. Claro que esta cópia exige que seja feita para outro disco. A cópia normalmente é feita através do comando/programa
dd.