Windows 8 Not Shutting Down Properly With Fast Start-Up Enabled

While Fast start-up is enabled, on turning the computer off (shutdown) the computer idles for about 5min after logging out/screen turning off. It then turns off. On returning into Windows I receive the error message saying Windows didn't shut down properly.

Hibernate works fine, and I am told this shouldn't be the case - If one doesn't work, neither should. It works when both Fast start-up is enabled and disabled, as does restart and sleep.

Windows is installed under UEFI.

The UEFI ultra fast boot option for my motherboard cannot be enabled as my GPU doesn't support some UEFI GOP tech. As far as I know, not related to windows fast start-up, but thought it was worth mentioning.

To clarify, if this: http://www.eightforums.com/tutorials/6320-fast-startup-turn-off-windows-8-a.html is enabled, the computer does not shut down properly.

EDIT: Some more information on the matter:

Formatting didn't fix the issue. Still fails regardless of drivers installed.

Hardware was purchased ~6months ago. Running a good SSD.

Event viewer

Always these two messages in close succession:

Error (event ID 6008): The previous system shutdown at 7:45:21 PM on ‎27/‎10/‎2012 was unexpected.

Critical (kernel power, event ID 41): The system has rebooted without cleanly shutting down first. This error could be caused if the system stopped responding, crashed, or lost power unexpectedly.

Update

Upon installing WPT as suggested below to figure out what was happening during shutdown, and running the cmd

xbootmgr -trace shutdown -noPrepReboot -traceFlags BASE+CSWITCH+DRIVERS+POWER -resultPath C:\TEMP

Windows fast start-up is now working consistently. Still works upon uninstalling WPT. This is the only change to occur on the computer. Nothing else has bee installed/uninstalled, no Windows Updates, nothing. Windows fast start-up did not work prior to installing WPT and running the cmd (made sure I tested).

Update 2

Since a random patch to Windows Defender, computer has again been failing to shut down properly. The above "fix" didn't work this time around.

Update 3

Latest update to Windows Defender has fast stat-up working again.

Update 4

Computer shutting down properly is now completely inconsistent.

Use xbootmgr from the WPT to trace which the shutdown is slow:

http://www.msfn.org/board/topic/158252-trace-why-windows-8-boots-shutsdown-or-hibernate-slowly/

Generate the Shutdown and Hibernate XML and look what takes so much time.

Looks to be an issue surrounding Windows Update... Ensuring there are no updates waiting to be downloaded/installed at point of shutdown, I haven't had a problem. This is the closest I've come to 'solving' the issue.