Ubuntu 16.04.1 WiFi works only after several reboots
If you can change the router encryption, change it to WPA2-PSK or WPA2-AES only, no WPA, WEP, or TKIP.
Then disable UFW as it is blocking mDNS traffic.
Reboot and see if the issues are gone, if not then we can disable the power management with
sudo sed -i 's/wifi.powersave = 3/wifi.powersave = 2/' /etc/NetworkManager/conf.d/default-wifi-powersave-on.confThen reboot again and see if it is fixed