They should all be in the same place, for any games th125+ that you have.
Have you saved a replay in those games yet? Perhaps it doesn't appear until you've saved at least one replay...
Also, for th13, have you updated it to v1.00c? If I recall correctly, ud replays didn't work properly in the initial release of the full version. (Edit: Though that wouldn't be the problem, since you'd have to place the replay in the folder to find out it doesn't work...)