When installing the server on a clean Debian machine, an error was given by the InitDB script when it was trying to create the databases (unfortunately I don't have a copy of that error any more).

Luks helped me resolve this via IRC, by creating the database manually in psql using the following command:

CREATE DATABASE musicbrainz_db WITH OWNER = musicbrainz TEMPLATE template0 ENCODING = 'UNICODE' LC_CTYPE='en_GB.UTF-8' LC_COLLATE='en_GB.UTF-8';

Should the InitDB script be creating the database this way too, in case anyone else runs into the same problem?