Você tentou atualizar-rc.d?
Quando você executa sudo update-rc.d php5-fpm defaults php5-fpm vai começar na inicialização.
Quando eu reinicio meu Ubuntu 12.04, o php5-fpm não é executado automaticamente. No entanto, o nginx começa automaticamente.
Estou usando o soquete Unix em vez de TCP \ IP
Esta é a saída de /etc/init.d/php5-fpm status após uma reinicialização do servidor:
/etc/init.d/php5-fpm status
* php5-fpm não está sendo executado