Tivemos o mesmo problema e não sabemos ao certo o que causou isso.
Nós tentamos reinstalar via apt-get , depois da limpeza, sem sucesso.
Baixamos a versão pré-compilada de 64 bits do site do MongoDB e tentamos executar mongod desse pacote, e tudo começou bem. Você provavelmente vai querer ficar com a versão 2.0.4 - usamos este arquivo.
Nós movemos os arquivos em bin/ para /usr/bin e o mongod estava sendo iniciado corretamente novamente.
Esta não é uma boa solução, mas funciona.