After trying some experiments and solutions at pcgamingwiki website when nothing worked i experimented on my own. I read about Xliveless which allows xlive without actually having xlive.
I pasted xlive.dll into Gears Of War Binaries folder and started the game. It worked perfectly and saving also works.
Fix:
Download Xliveless package from internet or links below. Extract xlive.dll and paste into Gears Of war Binaries folder. If it doesn't work then set compatibility mode to older windows.
Xliveless link:
I don't remember from where is got mine Xliveless but mine xlive.dll has size of 209,920 bytes and its x86 i.e. 32 bit dll. Try this exact file version and game should work.