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.