wifi and/or ethernet does not work roughly half of the times

After booting, roughly half of the times, wifi doesn't work: The nm-applet menu looks as if no wifi would exist. Instead, it lists the a non-existing cable network device called "Marvell 88W8897 [AVASTAR] 802.11ac Wireless". (The network manager seems to be trying to connect to that device, but fails.)

After doing
  /etc/init.d/network-manager restart
the wifi device is always recognized properly, so I guess it's something happening in the wrong order during booting. (Alternatively, unloading and reloading the kernel module mwifiex_pcie also always helps.)

The problem did not exist in ubuntu 15.10.

Some more information:

$ lsb_release -rd
Description: Ubuntu 16.04 LTS
Release: 16.04

When the bug is there:

$ nmcli d show wlp1s0
GENERAL.DEVICE: wlp1s0
GENERAL.TYPE: ethernet
GENERAL.HWADDR: 50:1A:C5:E8:2F:09
GENERAL.MTU: 1500
GENERAL.STATE: 70 (connecting (getting IP configuration))
GENERAL.CONNECTION: Kabelnetzwerkverbindung 2
GENERAL.CON-PATH: /org/freedesktop/NetworkManager/ActiveConnection/7
WIRED-PROPERTIES.CARRIER: on

$ ifconfig -a
lo Link encap:Local Loopback
          inet addr:127.0.0.1 Mask:255.0.0.0
          inet6 addr: ::1/128 Scope:Host
          UP LOOPBACK RUNNING MTU:65536 Metric:1
          RX packets:3380 errors:0 dropped:0 overruns:0 frame:0
          TX packets:3380 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1
          RX bytes:251184 (251.1 KB) TX bytes:251184 (251.1 KB)

wlp1s0 Link encap:Ethernet HWaddr 50:1a:c5:e8:2f:09
          UP BROADCAST MULTICAST MTU:1500 Metric:1
          RX packets:0 errors:0 dropped:0 overruns:0 frame:0
          TX packets:0 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1000
          RX bytes:0 (0.0 B) TX bytes:0 (0.0 B)

After restarting the network manager:

immi@flunder:~$ nmcli d show wlp1s0
GENERAL.DEVICE: wlp1s0
GENERAL.TYPE: wifi
GENERAL.HWADDR: 50:1A:C5:E8:2F:09
GENERAL.MTU: 0
GENERAL.STATE: 100 (connected)
GENERAL.CONNECTION: virginmedia4709476
GENERAL.CON-PATH: /org/freedesktop/NetworkManager/ActiveConnection/8
IP4.ADDRESS[1]: 192.168.0.3/24
IP4.GATEWAY: 192.168.0.1
IP4.ROUTE[1]: dst = 169.254.0.0/16, nh = 0.0.0.0, mt = 1000
IP4.DNS[1]: 194.168.4.100
IP4.DNS[2]: 194.168.8.100
IP6.ADDRESS[1]: fe80::521a:c5ff:fee8:2f09/64
IP6.GATEWAY:

(...)

wlp1s0 Link encap:Ethernet HWaddr 50:1a:c5:e8:2f:09
          inet6 addr: fe80::521a:c5ff:fee8:2f09/64 Scope:Link
          UP BROADCAST RUNNING MULTICAST MTU:1500 Metric:1
          RX packets:2 errors:0 dropped:0 overruns:0 frame:0
          TX packets:4 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1000
          RX bytes:304 (304.0 B) TX bytes:680 (680.0 B)

$ dmesg
(...)
[ 7.850180] IPv6: ADDRCONF(NETDEV_UP): wlp1s0: link is not ready
[ 7.850263] IPv6: ADDRCONF(NETDEV_UP): wlp1s0: link is not ready
[ 7.859773] IPv6: ADDRCONF(NETDEV_UP): wlp1s0: link is not ready
[ 7.869408] IPv6: ADDRCONF(NETDEV_UP): wlp1s0: link is not ready
(...)

I'm happy to try to fix the bug myself, but I could need some help: I don't know how to change booting order or something like that.

I could also temporarily insert some commands into /etc/init.d/network-manager printing some status information about the wifi, but I don't know how to get such status information.

ProblemType: Bug
DistroRelease: Ubuntu 16.04
Package: network-manager 1.1.93-0ubuntu4
ProcVersionSignature: Ubuntu 4.4.0-24.43-generic 4.4.10
Uname: Linux 4.4.0-24-generic x86_64
ApportVersion: 2.20.1-0ubuntu2.1
Architecture: amd64
CurrentDesktop: Unity
Date: Tue Jun 21 09:35:14 2016
IfupdownConfig:
 # interfaces(5) file used by ifup(8) and ifdown(8)
 auto lo
 iface lo inet loopback
InstallationDate: Installed on 2014-11-19 (579 days ago)
InstallationMedia: Ubuntu 14.10 "Utopic Unicorn" - Release amd64 (20141022.1)
IpRoute:
 default via 192.168.1.1 dev eth0 proto static metric 100
 169.254.0.0/16 dev eth0 scope link metric 1000
 192.168.1.0/24 dev eth0 proto kernel scope link src 192.168.1.50 metric 100
NetworkManager.state:
 [main]
 NetworkingEnabled=true
 WirelessEnabled=false
 WWANEnabled=true
 WimaxEnabled=true
SourcePackage: network-manager
UpgradeStatus: Upgraded to xenial on 2016-04-30 (51 days ago)
modified.conffile..etc.NetworkManager.NetworkManager.conf: [modified]
mtime.conffile..etc.NetworkManager.NetworkManager.conf: 2014-12-13T12:54:55.927900
nmcli-dev:
 DEVICE TYPE STATE DBUS-PATH CONNECTION CON-UUID CON-PATH
 eth0 ethernet connected /org/freedesktop/NetworkManager/Devices/0 Kabelnetzwerkverbindung 1 d3ba9191-d126-453b-99a5-1bd12ed71d33 /org/freedesktop/NetworkManager/ActiveConnection/1
 wlp1s0 wifi unavailable /org/freedesktop/NetworkManager/Devices/2 -- -- --
 lo loopback unmanaged /org/freedesktop/NetworkManager/Devices/1 -- -- --
nmcli-nm: Error: command ['nmcli', '-f', 'all', 'nm'] failed with exit code 2: Error: Object 'nm' is unknown, try 'nmcli help'.