If you used sysv-rc-conf to add a service to a runlevel (/etc/rc?.d), or did it manually,
the service may be missing dependencies and refuse to start. (For some reason rc.local is
affected by this, even though it should have no dependencies since it's just a simple
shell script. I dunno.)

Run

insserv /etc/init.d/<servicename>

to fix this.