Dan and Rangerat..
I have been trying to precisely identified what changed that corrected my computer after about 4 days suffering the same thing you have. My improvement happened after a Tuesday, a day of the week that Microsoft offers fixes (I think). I noticed that the upgrades were not happening upon shut down and I found a place to install upgrades before shutting down. I also started to review the installed Knowbase upgrades that "might" help your situation. Right now my short list is KB2887595, KB2538242, KB2267602, KB 2883200, KB2903939, KB2887595, KB2884846. These upgrades "gradually" made it onto my computer, and each time it functioned better. However, none of these were installed during that magic moment that my computer began to start up extremely well. There are places in the windows log where it desired to install these, but it took that "manual installation" to finally get 21 upgrades to install. I have already forgotten what buttons I pushed (control panel, .... upgrades... install now...). But that is what worked. There are also logs that you can read and there are directions out there how to reach them. Finally, after initially not opting to be part of the Microsoft Customer Improvement, the day before the improvement, I changed that option and accepted to be part of the Microsoft Customer Improvement program which sends anonymous operating data to MS. As frustrated as we can get, Microsoft does seem to have an excellent operating system this time. There is something peculiar about 8.1 Professioinal that affects some machines.
Check your update installation log. If it is blank, try updating manually and see it helps. If it does, we will have a better idea towards a solution to this problem.
Fortunately for me the "magic" solution was to disable the Atheros Bluetooth drivers. Immediately boot up 10 seconds and shutdown 10 seconds on a laptop with HDD not SSD.
No problems with updates before or after.
The speed for boot and shutdown with the Win 8 as delivered was also 10 seconds. It was after the full win 8 update and then win 8.1 upgrade that everything slowed down to about 5 minutes or more to shutdown. No problems any more.