The version of NIS to be shipped with Debian 4.0 has support for Network Manager in ypbind, the program responsible for ensuring that NIS client systems can access a NIS server. Unfortunately Network Manager is targeted at client systems with dynamically assigned addresses and does not support some common network configurations, particularly static ones. When Network Manager is run on a computer with such a configuration it presents misleading information to NIS, causing NIS to think that it is not connected to a network and fail to connect to a server.
In order to avoid these problems the version of NIS in etch disables Network Manager support by default but the configuration file with this change is not updated automatically on upgrade. To disable Network Manager support by hand edit the configuration file /etc/default/nis to add -no-dbus to YPBINDARGS:
# Additional options to be given to ypbind when it is started.
Uninstalling the network-manager package if it is not in use will also resolve the problem.
This also applies to the packages currently scheduled for release in the next version of Ubuntu (codenamed Feisty).