Thw Wireless network adapter is only occasionally recognized as such, in most cases it is recognized as a wired connection (according to NetworkManager) and does not work. See also: http://askubuntu.com/questions/777962/no-wireless-with-broadcom-bcm4350-ubuntu-16-04/779091#779091
Update: even with 4.4.1-040401-generic it doesn't always works, just probably more often than with other versions (didn't reboot often enough to present robust statistical evidence).
Can you provide your kernel config file. Also output of 'lspci -v' would be useful.
Created attachment 218971 [details] kernel 4.4.0-22-generic config - this kernel mostly fails
Created attachment 218981 [details] lspci -v output for kernel 4.4.0-22-generic