Have you patched the game to version 1.4? You also might want to try the Xliveless thing, it might bypass whatever is stopping you. I believe the current version is .97b. It can be found on google, and it;s easy to install. Just replace the xlive.dll in your game folder with the one from Xliveless.
You should manually download and apply patch 1.4 just to be safe. Now for Xliveless. Right-click your GTAIV icon and select Properties. Click the tab Open File Location. This should take you to the games folder, where the bad xlive.dll is. Now all you have to do is drag the Xliveless xlive.dll from wherever you downloaded it to, and drop it in the game folder and click Yes to replace it.