I just got Gears Of War, I put it in and it told me it needed an update for it. I accepted and it downloaded, once it got almost done, I got an Update Failed message and told me to go to xbox.com/support.
Why???

There's a way to clear the cache files, but I don't have it bookmarked, if I had a 360 I would probably remember the sequence, it might help doing this.

A quick search here about cache clearing and I got:

"I can provide a little more context on this. Clearing out your system cache:
* Will clear out the temporary copies of achievements and gamertiles on Memory Units or Hard Drives (note these get re-downloaded when re-connected to Xbox Live)
* Will clear out Game Updates stored on Memory Units or Hard Drives. (note these will get re-downloaded when launching that Game while connected to Xbox Live)
* Will not clear out system updates.
* Will not clear out the game areas of the hard drive where game titles cache their own information"

The last sentence indicates it might not help you by doing this, as it seems game cashe isnt being cleared.

Anyway, clearing is done like this:
"Go to the system blade and then memory. Press Y on either the HDD or a MU and then press X,X,Left Bumper, Right Bumper, X,X. Once you do this a blade will pop up saying: This will perform maintenance on your Xbox 360 storage devices. Do you want to continue? Pick yes or no."

What happends if you turn off the console, turn it on again and inserts GoW a second time? Does it try do update again, or just tell you it failed and to go to the support page ?

...so you came to xbox-scene.

lol anyways, do the above methods, also try loading the game without the harddisk or memory unit. then turn off plug everything back to try again...

have you tried to play it again after that? it will probably just downlaod it again and try to install it again