We have recently seen an increase in issues relating to the keys customers are receiving from the Steam Client not working to sign-in from within the game. After looking into this issue, we have identified the cause and solution.
If you purchased the Grand Theft Auto IV over the last few weeks (starting around August 20th of this year - 2012) and are getting a message in game that the key from Steam is invalid; It seems that the type of code being given by the Steam client is now a redemption code which can be redeemed here on Xbox.com (https://live.xbox.com/RedeemToken?xr=shellnav)
Once the code has been redeemed you can simply sign in to the Games for Windows Marketplace, go to the downloads tab, GTA 4 should now be there so click on it and then select 'View Game Keys' and it will show the code to log you in, in game.
You do not need to reinstall the game, simply press Play in Steam and if it asks for the code when you try to sign-in, input the one from the Games for Windows Marketplace.
Also you now key now download and install the game through the marketplace if you want.
Okay, There seem to be two separate issues people are experiencing.
A) Bought the game during the Steam Summer Sale:
B) Just recently purchased the game and when you try to redeem it on the website you get an error similar to "There is a problem with the offer associated with this code"
We have confirmed that this is also now the case with new retail disc copies of the game. If you purchase a disc copy of the game and you get an invalid key message when you enter the code from the back of the manual, please try to follow the process above to redeem the key here on Xbox.com and then get the Game Activation Key from the Games for Windows Marketplace.
Again if all of that is correct and you still get the same error message, please wait 72 hours before trying again. Then you may either contact your retailer (such as Steam support) or Games for Windows Live support and work with them to verify the key you have and try to get you a working key.
This now applies to all Grand Theft Auto IV games. Meaning that if you buy either GTA4 or GTA4: EFLC, either from Steam or the retail disc copies, you will now get a redeem code you get on Xbox.com.
Then after you have redeemed it, you will need to open the Games for Windows Marketplace, go to the downloads tab, select your game, then hit 'View Game Keys' to get your access key to sign in to Games for Windows LIVE.
As before you do not need to uninstall or reinstall the game, you will just need the code from the Games for Windows Marketplace.
9/11/2012 - Edited to add solutions for people experiencing difficulties.
10/5/2012 - Edited with info that this is also now the case with retail copies
11/9/2012 - Edited with updates for EFLC