Comment 2 for bug 1487679

I have this problem as well, or at least a related one. On my system systemd resolves the cycle by disabling NetworkManager, so I have no internet until I systemctl start NetworkManager. Here's the relevant section of the log:

Feb 04 12:17:32 Behemoth systemd[1]: network-online.target: Found ordering cycle on network-online.target/start
Feb 04 12:17:31 Behemoth mtp-probe[583]: bus: 2, device: 4 was not an MTP device
Feb 04 12:17:32 Behemoth systemd[1]: network-online.target: Found dependency on NetworkManager-wait-online.service/start
Feb 04 12:17:33 Behemoth nvidia-persistenced[684]: Started (684)
Feb 04 12:17:32 Behemoth systemd[1]: network-online.target: Found dependency on basic.target/start
Feb 04 12:17:33 Behemoth nvidia-persistenced[684]: Failed to query NVIDIA devices. Please ensure that the NVIDIA device files (/dev/nvidia*) exist, and that user 121 has read and write permissions for those files
Feb 04 12:17:32 Behemoth systemd[1]: network-online.target: Found dependency on paths.target/start
Feb 04 12:17:33 Behemoth nvidia-persistenced[684]: The daemon no longer has permission to remove its runtime data directory /var/run/nvidia-persistenced
Feb 04 12:17:32 Behemoth systemd[1]: network-online.target: Found dependency on cups.path/start
Feb 04 12:17:33 Behemoth nvidia-persistenced[684]: Shutdown (684)
Feb 04 12:17:32 Behemoth systemd[1]: network-online.target: Found dependency on sysinit.target/start
Feb 04 12:17:32 Behemoth systemd[1]: network-online.target: Found dependency on nbd-client.service/start
Feb 04 12:17:32 Behemoth systemd[1]: network-online.target: Found dependency on network-online.target/start
Feb 04 12:17:32 Behemoth systemd[1]: network-online.target: Breaking ordering cycle by deleting job NetworkManager-wait-online.service/start

This is a regression from 15.04 to 15.10.