ok i think i need to screenshot it for you seeing it really is simple and i can't see where you're going wrong.
All i can think of is that you are saving the game and NOT saving replays, if you are playing online you are pissing everyone off by doing so.
This means all those "replays" you saved arn't replays, but are saved games and you can load them. In fact i believe it's possible to retrieve the replay from the save file, so all those games you saved i'm fairly sure you can get the replay for.
Anyway the basics:
Let us say you have left a game mid way through, but you still want to keep the replay. So you select QUIT.

Next, we need to click on SAVE REPLAY and not just skip through this part (which is what i guess you usually do):

Give the replay a name, not adding the image here as i only get 3 image slots.
http://img707.imageshack.us/img707/5429/rep3q.jpgThe replay has not been saved after clicking save. To load it, go to where you found "lastreplay" and select it:

Voila you are viewing the replay.
Let me know if this works. If it does then i will consider letting you know how to get the replays out of your saved games. Are these games online?! May make a difference, need to check as i'm unsure myself.