Comment 42 for bug 543506

I think I can give some more light on the subject. If you are having the same problem as me then it is an intermittent problem that affects ALL services that are started through rc-sysinit, either all starts or none.

The reason is that rc-sysinit is started when the "lo" network device is started, se bug 543506 for a related problem, and now upstart is sometimes not getting the event that it has happened. Steve Langasek noted that NetworkManager is starting "lo" if it is not already started but not notifying upstart. (https://bugs.launchpad.net/ubuntu/+source/upstart/+bug/461725/comments/18)

So now we have two entities that will start "lo" /etc/init/network-manager.conf and /etc/init/networking and their starting order is not defined causing a race condition. If networking is started before network-manager then it works otherwise not.

Three options exist:
1. correct NetworkManager so that it is notifying upstart
2. set NetworkManager to wait for networking.
3. both

I have personaly opted for #2 and changed /etc/init/network-manager.conf to contain:
start on (local-filesystems
              and started dbus
              and started networking)