We had the same problem. We played, then we saved the replay. It prompts us a name for the replay file.
However, going to "recorded games", we are unable to find any entries at all, never mind the replay file we saved. This occurs both on the client and server computer.
Thanks for any advice!