I had this exact same problem, the fans would start blowing at 100% as soon as the card got a little warmed up from a game.
I too could only fix this by rebooting, or uninstalling the driver, otherwise the fans would keep going at 100%. Also, I did never get readings for fan speeds, not in Afterburner and also not in GPU Tweak II, went through a lot of versions for both softwares and it was always the same.
Setting the fans to a speed of 50%, for example, resulted in the card going to leaf blower mode again.
I had a GTX 970 installed before the 1080 with latest drivers. I tried all kinds of different driver versions, always with a clean uninstall followed by a proper reboot before I installed another one, nothing would help. I was close to assuming the card is faulty, but it wasn't.
I actually fixed my issue with DDU / Display Driver Uninstaller; just google it, I'm not sure whether it's allowed to post external links on here. I ran the tool in safe mode and voila, after it was done, the latest driver 368.69 worked fine and I got fan speed readings and could also manipulate fan speeds in Afterburner and GPU Tweak II.
I hope this helps someone, this problem was driving me nuts. I'm not sure what went wrong by simply uninstalling the drivers, I've done this a lot of times with a lot of cards and never ran into this kind of problem, but the DDU thing sure did work fine and removed something, from the registry maybe, I dunno, that was messing with the 1080.
System specs:
ASUS P9X79 Deluxe running on an Intel i7 3930K and a Strix GTX1080-A8G-Gaming; BIOS Verison: 86.04.17.00.E3 on Win10 Pro 64Bit (Had the same issue on the same setup using Win7 Pro 64Bit).