Comment 12 for bug 1582986

I can confirm I'm getting this error too. Althou it seems to be a bit random I can confirm I didn't get it in Ubuntu 12.04.
I wish I could be more precise but I can't tell if this is something caused by other process... so I can't tell if started happening on 16.04 or after installing some package.

Ubuntu 16.04
3.13.0-92-generic
NetworkManager --version: 1.2.2

Here I paste some interesting lines from dmesg:

-----
[ 19.350616] systemd[1]: network-online.target: Found ordering cycle on network-online.target/start
[ 19.350623] systemd[1]: network-online.target: Found dependency on NetworkManager-wait-online.service/start
[ 19.350628] systemd[1]: network-online.target: Found dependency on NetworkManager.service/start
[ 19.350631] systemd[1]: network-online.target: Found dependency on basic.target/start
[ 19.350634] systemd[1]: network-online.target: Found dependency on sockets.target/start
[ 19.350638] systemd[1]: network-online.target: Found dependency on uuidd.socket/start
[ 19.350641] systemd[1]: network-online.target: Found dependency on sysinit.target/start
[ 19.350645] systemd[1]: network-online.target: Found dependency on firestarter.service/start
[ 19.350648] systemd[1]: network-online.target: Found dependency on network-online.target/start
[ 19.350654] systemd[1]: network-online.target: Breaking ordering cycle by deleting job NetworkManager-wait-online.service/start
[ 19.350659] systemd[1]: NetworkManager-wait-online.service: Job NetworkManager-wait-online.service/start deleted to break ordering cycle starting with network-online.target/start
[ 19.350750] systemd[1]: network.target: Found ordering cycle on network.target/start
[ 19.350754] systemd[1]: network.target: Found dependency on NetworkManager.service/start
[ 19.350758] systemd[1]: network.target: Found dependency on basic.target/start
[ 19.350762] systemd[1]: network.target: Found dependency on sockets.target/start
[ 19.350765] systemd[1]: network.target: Found dependency on uuidd.socket/start
[ 19.350768] systemd[1]: network.target: Found dependency on sysinit.target/start
[ 19.350771] systemd[1]: network.target: Found dependency on firestarter.service/start
[ 19.350775] systemd[1]: network.target: Found dependency on network-online.target/start
[ 19.350778] systemd[1]: network.target: Found dependency on network.target/start
[ 19.350781] systemd[1]: network.target: Breaking ordering cycle by deleting job NetworkManager.service/start
[ 19.350785] systemd[1]: NetworkManager.service: Job NetworkManager.service/start deleted to break ordering cycle starting with network.target/start
-----

I'm not sure if the problem is in NetworkManager service itself or if there is any other service messing around and causing these "ordering cycles" which seems to end killing the NetworkManager process.