NetworkManager wont start at system boot

From time to time NetworkManager does not start at system boot.

NetworkManager seems to be started, but being terminated immediately.
Symptoms:
* no network connection at system boot.
* no network connection while logging in.
* no network applet after logging in.

NetworkManager isn't running after logging in.
I have to execute "service NetworkManager restart".

Problem:
* since NetworkManager not running at system boot it is not possible to connect the system via ssh! You will need a console. Bad with headless servers: you are locked out of them after rebooting.

Workaround: write a script trying to start NetworkManager every minute after reboot until it is running. Works so far, but it is a really bad hack!

Seen this problem on systems migrated from Ubuntu 14.04.5 LTS to 16.04.1 LTS.

ProblemType: Bug
DistroRelease: Ubuntu 16.04
Package: network-manager 1.2.2-0ubuntu0.16.04.3
Uname: Linux 4.8.6+ x86_64
ApportVersion: 2.20.1-0ubuntu2.1
Architecture: amd64
Date: Tue Nov 1 22:13:15 2016
InstallationDate: Installed on 2011-10-19 (1840 days ago)
InstallationMedia: Xubuntu 11.10 "Oneiric Ocelot" - Release amd64 (20111012)
IpRoute:
 default via 192.168.6.1 dev enp4s0 proto static metric 100
 169.254.0.0/16 dev enp4s0 scope link metric 1000
 172.19.1.0/24 dev vmnet1 proto kernel scope link src 172.19.1.1
 172.19.8.0/24 dev vmnet8 proto kernel scope link src 172.19.8.1
 192.168.6.0/24 dev enp4s0 proto kernel scope link src 192.168.6.46 metric 100
NetworkManager.state:
 [main]
 NetworkingEnabled=true
 WirelessEnabled=false
 WWANEnabled=true
 WimaxEnabled=true
SourcePackage: network-manager
UpgradeStatus: Upgraded to xenial on 2016-09-08 (54 days ago)
mtime.conffile..etc.NetworkManager.NetworkManager.conf: 2013-03-03T12:29:43.912070
mtime.conffile..etc.init.network-manager.conf: 2013-03-04T17:15:37.443693
nmcli-con:
 NAME UUID TYPE TIMESTAMP TIMESTAMP-REAL AUTOCONNECT AUTOCONNECT-PRIORITY READONLY DBUS-PATH ACTIVE DEVICE STATE ACTIVE-PATH
 muc-ews e0d03730-1e06-4998-b508-157a5a2a2ad0 802-3-ethernet 1478034710 Die 01 Nov 2016 22:11:50 CET yes 0 no /org/freedesktop/NetworkManager/Settings/1 yes enp4s0 activated /org/freedesktop/NetworkManager/ActiveConnection/0
 CVJM 0eaf8330-35e8-4eae-a922-16f0547f5c87 802-11-wireless 0 never yes 0 no /org/freedesktop/NetworkManager/Settings/0 no -- -- --
nmcli-nm:
 RUNNING VERSION STATE STARTUP CONNECTIVITY NETWORKING WIFI-HW WIFI WWAN-HW WWAN
 running 1.2.2 connected started full enabled enabled disabled enabled enabled