The default scripts fire off ypbind and yppasswdd before launching ypserv. This, obviously, does not work on the NIS server. A simple workaround (I don't know if it's correct or not, but it does fix the problems) is to renumber the start and kill scripts to switch ypbind and ypserv. Probably, yppasswdd should start after ypbind as well, but I haven't yet had problems with them reordered.
this has been fixed in a later release of ypserv. (1.3.5-3, IIRC)