I've got a lot of problems for opening replays.
I've always got those errors

And half of the time, toribash lag & crashes.

I've tried deleting .rpl extension (using this), rebooting, and reinstalling with administrators rights, but nothing changed.

Bump.
I'm on Windows Vista.

Up.
It works when it's in the toribash replays folder.

Open your replays manually, and delete those who don't open, they might corrupt the game.

What the, I cant believe none was around to help you for four days...

I'm guessing there's a problem with associating .rpl files to Toribash.

The only way you can do it is to completely remove toribash (every single version), then reboot to refresh the registry and install the newest version again.

That should do the trick.

And how do I remove toribash ?
Because there are no uninstallers.

Just delete the folders, no need to uninstall.

Indeed, go to C:\Games\ then delete all Toribash folders, however backup the replays if you want to keep those.

It didn't work, and I tried twice, with and without administrator rights.

Download a older version of Toribash first, I.E like 3.86 or a closer version to that. It may just be your 3.9 Client and depends if it's the Beta version or not.