Got the exact same error code.
Playing MW3 and xbox live disconnected.
Plugged in the ethernet cable and fired it back up.
Live was okay, but I couldn't access my cloud storage.
Googled the error code 80004004 and it brought me here.
Edit -- waited 5 minutes (while i was doing this) and restarted. It loaded after the restart.