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.