O problema era que o arquivo PID não estava sendo excluído depois que eu parei o carbon-cache.py, ou seja, não foi reiniciado.
Depurei o problema verificando os logs em /var/log/multilog/carbon-cache/current
que mostravam que o arquivo PID existe.
Após excluir o arquivo PID, o problema foi resolvido completamente.