It is not a common issue with the NUCs with Microsoft® operating system. Intel noted random issues with some memories; please do this work around and keep us posted with your findings.
Go to BIOS>Advanced>Performance>Memory> and uncheck the option Round Trip Latency Optimization
I have tried changing the option Round Trip Latency Optimization, but the behaviour keeps on.
I have bought another nuc, and, with Ubuntu 15.10, it shutdowns fine. The problem is that I have to use 14.04 LTS in the first NUC.
It is strange because it fails every two shutdowns, it does wrong the first one and fine the next.
I hope there is something else to try. Regards.