UPDATE: It seems that as of 16.04.1 this is not an issue for me any more. There have been plenty of reports regarding WiFi issues on Ubuntu 16.04. The majority of issues seems to stem from suspend/resume issues where the network would not re-connect, show the wrong icon in the top bar or similar. The temporary workaround for this is to restart the network manager if you have no network at all, or, if you have network but the nm applet is showing the wrong status, just restart the nm applet.