Grazie per la risposta paolino.
Sono riuscito a farlo funzionare mentre stavo per risponderti.
Mi inviava messaggi in /var/log/root dicendo di non riuscire a creare i file di lock, infatti mancava la cartella, l'ho creata e sistemato i permessi ed ha iniziato a funzionare.

Nel file di log segnalava dei warning relativi a send_mail, ed ho installato postfix, e munin ha smesso di nuovo di funzionare:

2012/03/25 22:55:01 Opened log file
2012/03/25 22:55:01 [INFO]: Starting munin-update
2012/03/25 22:55:02 Failed to connect to node 127.0.0.1:4949/tcp : Connection refused
2012/03/25 22:55:02 [ERROR] Munin::Master::UpdateWorker<localdomain;localhost.localdomain> failed to connect to node
2012/03/25 22:55:12 [WARNING] Call to accept timed out.  Remaining workers: localdomain;localhost.localdomain
2012/03/25 22:55:12 [INFO] Reaping Munin::Master::UpdateWorker<localdomain;localhost.localdomain>.  Exit value/signal: 20/0
2012/03/25 22:55:12 [INFO]: Munin-update finished (10.05 sec)

EDIT:
Ho appena notato che è sparita la cartella che avevo creato, e in /var/mail/nobody ho lo stesso messaggio che avevo visto all'inizio.
Adesso ho ricreato la cartella, anche se non capisco perchè la cartella sia sparita.
Ma contrariamente a quanto mi aspettavo continua a non funzionare, e nei log ho sempre quell'errore di timeout che ho riportato sopra.

Quindi inizialmente non riusciva proprio a partire. Mi sa che è un problema di permessi. Qual'è l'utente assegnato al server munin?

Suppongo non sia root chiaramente.

In realtà non avevo ancora modificato la configurazione di munin per farlo girare con un altro utente, e stà girando come root.
La cartella che ho dovuto creare in /var/run non riesce però a scriverla, devo impostare i permessi a 777 sulla cartella e dopo l'errore dei permessi sparisce.
E la cartella viene cancellata se riavvio il vps, e devo ricrearla.

Verifica se esiste un utente che potrebbe corrispondere a munin. Sto pensando che il programma si rifiuta di funzionare come root e forka un figlio assegnandolo ad un utente meno privilegiato.

Può sembrare un'idea stramba, però non si spiegherebbe altrimenti come sia possibile che non riesca a creare una banale directory ( girando come root ).

Il fatto che i messaggi arrivino nella mailbox dell'utente nobody avvalora questa tesi. Tieni presente che alcuni software ( postfix ad esempio ) girano come utente nobody. Magari munin pretende di fare lo stesso.

Esiste un utente ed un gruppo munin, ho modificato la configurazione e ora stà girando come utente munin e gruppo munin.
Non è riuscito a creare solo la cartella, e l'ho quindi creata manualmente e impostato come proprietario della cartella.
Ma continuo ad avere lo stesso problema.

Le email in uscita del vps non vengono consegnate, ma credo sia un problema relativo alla configurazione dns del dominio, che non ho ancora ultimato in quanto ho avuto qualche problema con la configurazione di bind. Potrebbe essere questo problema a farlo andare in timeout?

Se munin usa il domain name per accedere alla sua componente server e se bind ha problemi, allora è molto probabile.

L'unico modo per scollegare i due, è far usare a munin l'ip.

Ho provato a reimpostare la configurazione di bind, a quella originale di come mi è stato consegnato il vps, ma non è cambiato nulla.
Non sò più che provare a cambiare per farlo funzionare.

In primo luogo assicurati che il nome di dominio venga risolto in tempi "umani".

Dopo di che verifica quali processi avvia munin, se riesce ad avviarli correttamente e quali file usano.

Verifica la configurazione soprattutto. Perchè cerca di connettersi a 127.0.0.1? E soprattutto il server munin è configurato per stare in ascolto su 127.0.0.1:4949?

Facendo telnet 127.0.0.1 4949 ottengo la risposta corretta, come ho trovato dovrebbe essere nella documentazione di munin, per cui in ascolto sembra ci sia.

Usando il comando munin-check per vedere se trova qualcosa che non và, trova dei problemi sui permessi:

munin-check
Check /var/cache/munin/www
check /var/lib/munin/datafile
check /var/lib/munin/limits
check /var/lib/munin/localdomain
check /var/lib/munin/munin-graph.stats
check /var/lib/munin/munin-update.stats
Check miscelaneous
# /var/lib/munin/plugin-state : Wrong owner (munin != nobody)
# /etc/munin/plugin-conf.d : Wrong permissions (750 != 755)
Check done.  Please note that this script only checks most things,
not all things.

Please also note that this script is very new and may be buggy.

Però è configurato per girare come munin:munin per cui non ho capito il nobody da dove stà saltando fuori.

sembra un problema noto http://munin-monitoring.org/ticket/807

Non credo sia quello perchè:

root@server1:/var/lib/munin# ls -la
total 68
drwxr-xr-x  4 munin munin  4096 Mar 29 17:20 .
drwxr-xr-x 37 root  root   4096 Mar 25 23:58 ..
-rw-r--r--  1 munin munin 40201 Mar 29 17:20 datafile
-rw-r--r--  1 munin munin   847 Mar 29 17:20 limits
drwxr-xr-x  2 munin munin  4096 Mar 25 19:05 localdomain
-rw-r--r--  1 munin munin   222 Mar 29 17:20 munin-graph.stats
-rw-r--r--  1 munin munin    50 Mar 29 17:20 munin-update.stats
drwxrwxr-x  2 munin munin  4096 Mar 25 19:05 plugin-state

Quindi i permessi sono corretti credo, o no?
Ho comunque impostato a 775 tutta la cartella come indicato nel link che mi hai dato.

Ho appena controllato il grafico ed ha iniziato funzionare dalle ore 16 circa. Verso quell'ora avevo avviato il demone munin-node, che avevo visto non era avviato e con telnet inizialmente non rispondeva infatti. Non mi ero accorto che munin-node non si avvia automaticamente all'avvio, e quindi dopo l'ultimo riavvio che avevo fatto davo per scontato che continuasse ad essere in esecuzione.

Grazie mille paolino per l'aiuto.