In my case. I just deleted all the Gears of War folders I could find, but somehow it didn't go away (even used registry cleaner). After that, I tried pressing Uninstall and it went on, but.
Got the error: 0x80040702
Description: Failed to load DLL: FirewallInstallHelper (Not GameuxInstallHelper)
Setup will now terminate.
So I mounted the cd, then took the file FirewallInstallHelper.dll and posted it in the original Gears of War Folder.
In my case, C:\Programmer\Microsoft Games\Gears of War .. Then went on with the Uninstall, and it worked !?