Creating a database in Mongo: can't connect, get "connect failed"

I want to create a new database in Mongo. However, I'm having trouble connecting:

:~$ mongo
MongoDB shell version: 1.6.5
connecting to: test
Tue Dec 21 18:16:25 Error: couldn't connect to server 127.0.0.1 (anon):1154
exception: connect failed

How can I connect to mongo in order to create a new database? Alternatively, can I create a new database from the command line?

Slightly surprisingly, the Mongo docs don't seem to cover how to create a database.

Thanks.