I purchased Windows 8.1 Pro from Best Buy on Dec 26, 2013 and made the upgrade from Windows 7. My boot-up time from "off" to "sign-in" message is 15 minutes and 30 seconds. My shut down time is about 10 minutes. I installed the software on a Gateway FX6840. I have read the full string of suggestions. In my case using the "Charms" shutdown option turned the monitors off quickly, but the disk light and computer button light remained lit for 15 minutes or better. Using the "start" button (if that is correct name of the left hand lower icon) by right clicking and selecting shut down, the monitors (I have two monitors) remain lit with the "shutting down" message for 9 minutes and 35 seconds. I'll keep working at it; however, from what I can tell no one has identified the solution yet. I'll try other suggestions over the coming week and write another report. Once the system is booted up, the machine now flies. Hoping for a Microsoft update soon.
Counting myself and others on this forum, some of us have found solutions that are due to Bluetooth drivers. Before waiting for MS to provide a solution suggest you try disabling Bluetooth to see if that resolves the problem. Hoping for a quick resolution from MS is unrealistic.
This is not a fundamental Win 8.1 problem. I have two other Win 8.1 systems running with Bluetooth enabled and these have no problems. It is most likely specific Bluetooth drivers.