Primeiro de tudo, definitivamente fique com a versão 10gen do pacote - é muito mais provável que seja atualizado do que qualquer um dos repositórios de distribuição.
Em termos do erro, parece que o MongoDB está instalando corretamente, mas está falhando ao iniciar. Você não mencionou qual versão do Linux você está usando, mas desde que você está usando o apt-get então eu assumo que é um dos derivados do Debian, ou o próprio Debian é claro.
Para descobrir por que o MongoDB está falhando em iniciar, você precisará procurar nos logs pelo MongoDB. Isso pode ser diferente em seu sistema, mas o padrão é baseado no Debian mongod.conf seria:
/var/log/mongodb/mongodb.log
Procure no arquivo o motivo pelo qual ele não está sendo iniciado. Sinta-se à vontade para adicionar os detalhes à sua pergunta e eu posso acompanhar a causa, ou se ela é autoexplicativa (permissões, espaço em disco, etc.), então deixe-nos saber o que você precisou fazer para resolvê-la.
Finalmente, você deve notar que você pode estar correndo para este bug aberto:
Se o MongoDB estiver sendo iniciado com êxito, mas o comando de serviço ou o script de init acredita que ele está falhando, provavelmente você está sendo atingido por esse problema.