I'm also seeing the same problems running Ubuntu 16.04 on an Intel NUC6i5SYK. I installed Ubuntu a couple of days ago starting with kernel 4.4.0-21-generic, here the wifi worked most of the time. Updating to kernel 4.4.0-22-generic made this problem even worse. Now wifi doesn't work at all, even after several reboots. Booting with the previous kernel makes it work again...
I'm also seeing the same problems running Ubuntu 16.04 on an Intel NUC6i5SYK. I installed Ubuntu a couple of days ago starting with kernel 4.4.0-21-generic, here the wifi worked most of the time. Updating to kernel 4.4.0-22-generic made this problem even worse. Now wifi doesn't work at all, even after several reboots. Booting with the previous kernel makes it work again...