For a long time, I was unable to get the 'ssh' service to start up at boot time. I'll describe the problems I encountered, and then the solution. I used VMware Workstation v10.0.0.5 to create a 64 bit kali vm, installed from the latest (v1.1.0a) ISO.
Out of the box, brand new, 'rcconf' does not even show/list the 'ssh' service.
I could tweak the 'ssh' service with 'sysv-rc-conf', for run-levels 2, 3, 4 and 5. Reboot. 'rcconf' would then show the 'ssh' service.
It still didn't start at boot (by checking service status, and ps). Another check in sysv-rc-conf would show ssh as still be started for run-levels 2, 3, 4, and 5.
I looked into: "update-rc.d -f ssh enable 2 3 4 5" and that fixed the issue. The 'ssh' would be running after every reboot.
Another interesting detail: The magic line at the top of /etc/init.d/ssh, contains a space: "#!<space>/bin/sh". I removed the space in my VM for consistency, but thought you all should know.
