Just noting this down here for reference in case anyone else has a similar problem ...
I used 'Add Feature' to install Media Center in Win8, but during the restart I got the message that the update had failed.
I tried a second time and it was the same.
I searched about a bit and eventually found a reference to the log file: %localappdata%\Microsoft\Windows\Windows Anytime Upgrade\Upgrade.log
Checking this it turns out that before adding a feature, Win8 will install any outstanding updates; if one of these updates fails to install, then whole deal is rolled back.
Using Control Panel, I access the 'Classic' windows update screen (search Control Panel for 'Update') and performed the update manually. The 'EU Browser choice' update was failing, so I right-clicked and set a hidden (not an update I really need anyway).
After this, Adding the Media Center feature worked.