I also saw this problem while using Ubuntu 8.10 x86_64. I think I may have found the source of the problem.
I'm using this computer in a corporate environment, where each users home directory is mounted using autofs, and authentication is done using NIS.
The ssh daemon and automounting of the user's home directory failed to work after rebooting, but I found a workaround and a possible cause. This computer is using NetworkManager, which is loaded with /etc/rc2.d/S28NetworkManager. Autofs is loaded as /etc/rc2.d/S19autofs, and ssh as /etc/rc2.d/S19ssh, which are both loaded prior to NetworkManager.
The first thing I tried was to move autofs to S29, and ssh to S30 (both above NetworkManager). This should ensure that a network connection exists before starting the ssh and autofs daemons. However this did not work, for the following reason. If one runs '/etc/init.d/NetworkManager restart', this command will return several seconds before a network connection is established. The exit code it returns is 0, so there is no indication of an error.
As a test, I added the line 'sleep 15' near the end of /etc/init.d/NetworkManager (so this script would wait for 15 seconds before exiting), and rebooted the computer. Both the autofs and ssh daemons worked correctly after this.
I'm not proposing the NetworkManager script waits for 15 seconds, but instead it should wait until a network connection is either established or has failed, and return the appropriate exit code. Also, the NetworkManager init script should probably be placed before any other scripts that require a working network connection.