O que funcionou para mim no Ubuntu é uma combinação das respostas de @Tuan Nguyen e @Tom Carchrae
sudo kill $(sudo lsof -t -i:27017)
sudo rm -rf /tmp/mongodb-27017.sock
sudo rm -f /var/lib/mongo/mongod.lock
sudo rm -f /var/run/mongodb/mongod.pid
sudo mkdir -p /var/run/mongodb/
touch /var/run/mongodb/mongod.pid
sudo chown -R mongodb:mongodb /var/run/mongodb/
sudo chown mongodb:mongodb /var/run/mongodb/mongod.pid
Você pode então executar
sudo service mongod start