GTA4 saves are hashed by Xlive. They will only work on a specific machine configuration/user which is why you aren't having any luck loading your old saves. There is a way around this. You need to seek out an Xlive wrapper, which is a little tool designed primarily for modders. This, among other things, will disable Xlive's save checking, and it will allow you to load any you want. That might be worth a look. As I see it, it's your only choice. You will, however, only need to run this once and not all the time. Once you have loaded your old save, you can re-save it in-game, and then remove the wrapper. Because it has been re-saved on your new setup, the game will be able to load it as normal from that point on, with no mods needed.
As for the save locations themselves, I can shed a little light on that too. By default, with xlive operating normally you will find them:
That is assuming a windows vista or 7 install (which I believe most of you have now). The windows xp install spot will be in the equivalent "Documents and Settings" directory. "installdrive" is the hard disk to which you installed the game. "user" is your currently logged on user name on which you load and play GTA4. "randomname" is a uniquely generated folder name based on your setup. Also note that "AppData" (or "Documents and Settings" in XP) is hidden in windows by default. You need to make a trip to Folder Options and tick to always show hidden files and folders.
Xlive wrappers/mods may change the save location, and make it more intuitive and readily accessible. If using one of these, you may find you saves moved to "Documents\Rockstar Games" or "Saved Games\Rockstar Games" (again, depending on your operating system). You may need to move out your old saves (from the default xlive spot) to the new location if you wish to use your old saves whilst utilizing the wrapper/mod. Hope that helps a bit