Comment 1 for bug 224828

I had this problem as well. By experimenting with the order in which the scripts in /etc/rc2.d/ are run, I discovered that if the /etc/init.d/nis script runs after the /etc/init.d/hal script, then NIS starts correctly, while if nis runs before hal, then it does not. This is apparently why the nis script runs successfully from the command line after booting. Thus, as a workaround, I did this as root:

cd /etc/rc2.d
mv S24hal S17hal

This puts hal before S18nis, and NIS starts correctly. I haven't noticed any side effects of moving hal, although I am not expert enough at what it might depend on to not be worried that my workaround might cause problems with other packages. I decided to move hal earlier rather than nis later, because S19autofs depends on S18nis, so I would have to move at least two scripts instead of one.

Just to reiterate the details of my setup: I unchecked "Enable roaming mode" and entered my static IP address; I added a line
  domain my-nis-domain server my.nis.server
to /etc/yp.conf. During boot, the nis script cannot bind to the nis server; it goes through the do_wait() loop. After booting, ypwhich continues to fail, despite the fact that ypbind is running:

lmunro@perish:~$ ypwhich
ypwhich: Can't communicate with ypbind
lmunro@perish:~$ ps -elfw|grep ypbind
5 S root 5203 1 0 80 0 - 7050 - 07:22 ? 00:00:00 /usr/sbin/ypbind
0 R lmunro 6292 6273 0 80 0 - 751 - 07:23 pts/0 00:00:00 grep ypbind
lmunro@perish:~$ cat /var/run/ypbind.pid
5203

At least in my case, I have no evidence that the network is not up at the time S18nis runs, whether or not hal goes first -- in fact, it obviously is up enough that ypbind can connect as long as hal has run first.