Comment 48 for bug 138691

SOLVED!

Finally, I got the whole thing working. In the end, the solution was simple: Disable/remove NetworkManager! Boot times actually seem shorter and shutdown works. NIS now comes right up (as opposed to with a delay with NetworkManager operating). To disable NetworkManager without removing it, do the following:

1) Make CERTAIN that your standard network interface is configured properly in /etc/network/interfaces. "systemsettings" was no help in doing so - I had to edit the file manually. In my case, there already was an entry for "eth0" - I just needed to add/uncomment the actual configuration. The complete entry looks like this:

  # The primary network interface
  auto eth0
  iface eth0 inet dhcp

Once this is done, the interface will be enabled during boot-up, despite NetworkManager being disabled.

2) Disable NetworkManager
Create two files in /etc/default:
echo "exit" > /etc/default/NetworkManager
echo "exit" > /etc/default/NetworkManagerDispatcher

3) Reboot

If everything went well, you should now have a working, NetworkManager-free network interface.

DOWNSIDES:
There are probably some potential downsides to disabling NetworkManager, especially if you want your machine to automatically switch between e.g. ethernet and wireless - as far as I understand that's precisely what NetworkManager was invented for. Hence, this situation does need "real" fixing at some point. However, if you have a workstation with a static network interface (in our case, even the laptops are used that way), there's no need for such functionality - just getting the interface up at boot time is sufficient.
Another downside is that the knetworkmanager icon does no longer work to indicate the status of the network connection. "knetstats" seems to do the job nicely, however.
As we don't need NetworkManager's functionality, there might be potential downsides that I have missed - YMMV, as always.

To the developers: If you need some additional input to try and debug the underlying NetworkManager problem, please let me know and I'll rig up a box that uses NetworkManager to test.