Wifi connections not available after system startup

[Portnov]

After system startup, in some cases (it seems randomly), network-manager does not show any connections available (empty list of networks in systray icon menu). If i press "configure connections" button, connections editor shows two connections, but it is not possible to activate any of them. Connections are called as "wired connection 1" and "Wired connection 2". If i go to connection settings, i can see that one of them is configured to use my ethernet cable interface enp0s25 (i usually have no ethernet cable attached), and another is configured to use my wifi interface wlp4s0. So it seems that problem is that for some reason network-manager "thinks" that my wireless interface is wired, and so does not even try to connect to any wifi network.
If I do sudo service network-manager restart, all becomes ok, network-manager immediately sees my wifi network and connects to it. But having to manual restart of service right after system startup indicates that something is very wrong.

This is newly installed Kubuntu 16.04 with latest updates.

What I tried to do:
* edit NetworkManager.conf to set [ifupdown] managed = true. No changes in behaivour at all.
* remove and install again network-manager package. For some time I thought that resolved the problem, but after few days it reproduced again.
* plug ethernet cable, connect to wired network, unplug cable. No results.

dmesg | grep wifi output:

[ 3.693651] iwlwifi 0000:04:00.0: Direct firmware load for iwlwifi-7260-17.ucode failed with error -2
[ 3.706221] iwlwifi 0000:04:00.0: loaded firmware version 16.242414.0 op_mode iwlmvm
[ 3.749453] iwlwifi 0000:04:00.0: Detected Intel(R) Wireless N 7260, REV=0x144
[ 3.749526] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
[ 3.749782] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
[ 3.965973] iwlwifi 0000:04:00.0 wlp4s0: renamed from wlan0
[ 4.329538] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
[ 4.330033] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
[ 4.535001] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
[ 4.535266] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
[ 122.272761] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
[ 122.273048] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
[ 122.470381] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled
[ 122.470640] iwlwifi 0000:04:00.0: L1 Enabled - LTR Enabled

Please ask if you need me to attach any other logs.

ProblemType: Bug
DistroRelease: Ubuntu 16.04
Package: network-manager 1.1.93-0ubuntu4
ProcVersionSignature: Ubuntu 4.4.0-22.39-generic 4.4.8
Uname: Linux 4.4.0-22-generic x86_64
NonfreeKernelModules: nvidia_uvm nvidia_modeset nvidia
ApportVersion: 2.20.1-0ubuntu2
Architecture: amd64
Date: Tue May 10 21:23:27 2016
IfupdownConfig:
 # interfaces(5) file used by ifup(8) and ifdown(8)
 auto lo
 iface lo inet loopback
InstallationDate: Installed on 2016-04-30 (9 days ago)
InstallationMedia: Kubuntu 16.04 LTS "Xenial Xerus" - Release amd64 (20160420.1)
IpRoute:
 default via 192.168.1.1 dev wlp4s0 proto static metric 600
 169.254.0.0/16 dev wlp4s0 scope link metric 1000
 192.168.1.0/24 dev wlp4s0 proto kernel scope link src 192.168.1.107 metric 600
NetworkManager.state:
 [main]
 NetworkingEnabled=true
 WirelessEnabled=true
 WWANEnabled=true
ProcEnviron:
 TERM=xterm
 PATH=(custom, no user)
 XDG_RUNTIME_DIR=<set>
 LANG=ru_RU.UTF-8
 SHELL=/bin/bash
SourcePackage: network-manager
UpgradeStatus: No upgrade log present (probably fresh install)
mtime.conffile..etc.NetworkManager.NetworkManager.conf: 2016-05-08T12:50:46.588618
nmcli-con:
 NAME UUID TYPE TIMESTAMP TIMESTAMP-REAL AUTOCONNECT AUTOCONNECT-PRIORITY READONLY DBUS-PATH ACTIVE DEVICE STATE ACTIVE-PATH
 tplink-portnov 1 fdff901c-5deb-4104-ba4d-c555e4b81d7c 802-11-wireless 1462897338 Вт 10 май 2016 21:22:18 yes 0 no /org/freedesktop/NetworkManager/Settings/0 yes wlp4s0 activated /org/freedesktop/NetworkManager/ActiveConnection/0
 Проводное соединение 1 08666419-d8c4-4c5f-911a-de123d44ec3a 802-3-ethernet 0 never yes 0 no /org/freedesktop/NetworkManager/Settings/1 no -- -- --
nmcli-dev:
 DEVICE TYPE STATE DBUS-PATH CONNECTION CON-UUID CON-PATH
 wlp4s0 wifi connected /org/freedesktop/NetworkManager/Devices/1 tplink-portnov 1 fdff901c-5deb-4104-ba4d-c555e4b81d7c /org/freedesktop/NetworkManager/ActiveConnection/0
 enp0s25 ethernet unavailable /org/freedesktop/NetworkManager/Devices/2 -- -- --
 lo loopback unmanaged /org/freedesktop/NetworkManager/Devices/0 -- -- --
nmcli-nm: Error: command ['nmcli', '-f', 'all', 'nm'] failed with exit code 2: Error: Object 'nm' is unknown, try 'nmcli help'.

[Portnov (portnov84)]

Also, I guess this bug may be somehow related to https://bugs.launchpad.net/ubuntu/+source/network-manager/+bug/1578533, which also reproduces for me on the same laptop.

[Launchpad Janitor (janitor)]

Status changed to 'Confirmed' because the bug affects multiple users.