After replying this this morning I updated to Windows 8.1 just to see if that would resolve anything. And, it seems that it did. I've shutdown, then turned on, the computer a dozen times just testing to see how quickly it shuts down. The shutdown is still longer than without Nod32 but it's now down to a pretty acceptable 15 seconds. Just in case anyone else stumbles on this the issue did not effect restart speeds. I will mark this as resolved a little later if this continues to work.