Eu lembro de um problema no empacotamento do debian há algum tempo, em que eles mudaram o local do pid. Também é possível que você alterou uma biblioteca compartilhada que está causando o nginx existente para não localizar o código no endereço recém-realocado. Você poderia fazer:
sh -x /etc/init.d/nginx stop
e veja qual é o erro na linha após start-stop-daemon
No pior dos casos, encontre o pid do nginx e faça um kill (ou se estiver preso, mate -9)
Nesse ponto, você deve ser capaz de reiniciar o nginx normalmente.