It worked just yesterday, and now I'm getting a desync error. The only thing I did since then is to download new maps using the beta launcher and play them.
1: If its an "Official" replay (from someone in beta) make sure you have the original base.sc2data file in your \StarCraft II Beta\Mods\Liberty.SC2Mod\ folder (its 709kb in size), your cache should be up to date since you where able to play it before. Make sure you are using the right base version as well.
2: If its a replay from someone else playing AI you have to have the maps line up and the same AI in your \StarCraft II Beta\Mods\Liberty.SC2Mod\ folder. To make sure the maps line up, you have to play a game on the map with the same AI setup. If the replay player is player 1 with AI's player 2 through 4, that is how you must preset the map then click play. You can quit out as soon as the game starts. If they have teams set, you too must set up the teams properly. The maps must be named the same as well. If you fixed mispellings or changed the map name in anyway, you must change it to match the replays map name.
Gl and HF
DrakeFS
It was indeed the sc2data file which was altered for some reason.