Just to get this technical note on the Internets for general helpfulness of humanity..
After following the main MongoDB instructions, I was stumped with "Error: couldn't connect to server 127.0.0.1 shell/mongo.js:79". Mongod had started but I couldn't 'mongo'. This was NOT a mongoDB problem, despite all the rest of the advice on the internet telling you to set the datadir, check permissions, uninstall the packages, try a different package etc.
I should have thought earlier to use my own brain. The problem was the server's own firewall preventing mongo from accessing port 27017. Specifically, the Rackspace sample iptables ruleset does not allow an SSHd user to 'mongo': Rackspace Cloud sample iptables.
So if you followed the official YouTube video on setting up your Rackspace Cloud server you'll hit this issue. Rackspace Cloud setup video by Chad. My cloud server is Ubuntu 10.04 Lucid but I expect any Rackspace cloud server configured as above will encounter this. To save you the hours of troubleshooting I've just undergone, this will sort you out:
[After following the MongoDB 'Quickstart' instructions and the stuff on the page above, installing from the mongodb-10gen package]
sudo iptables -A INPUT -p tcp --dport 27017 -j ACCEPT
sudo iptables -A INPUT -p tcp --dport 28017 -j ACCEPT
sudo iptables -A INPUT -s 127.0.0.1 -j ACCEPT
sudo iptables -A OUTPUT -s 127.0.0.1 -j ACCEPT
sudo bash -c "iptables-save > /etc/iptables.up.rules"
This assumes you followed Chad's instructions (around time 10:00) to reference /etc/iptables.up.rules from /etc/network/interfaces:
pre-up iptables-restore < /etc/iptables.up.rules
Do that, reboot your cloud server from the Rackspace web management interface - and you'll be able to 'mongo' on your server (and remotely).
Make sure you add 'auth = true' to /etc/mongodb.conf (also adding an 'admin' user via mongo) so that the web interface on http://www.yoursite.com:28017 isn't too useful to people.