I was having this same problem even with the correct map version downloaded. What I found out was some of the maps were renamed. It would say that I did not have the map "62_Hero_of_the_Empire". The problem was the download name was "62_Hero_of_the_Emp". I made a copy of that version and renamed it and it worked.
Another problem I came across was that some replays had their maps in a Hero of the Empire specific folder. I had to create a Hero of the Empire folder in the maps/downloads folder and put a copy of that version in there.
Just look at the exact name and location when it tells you that you are missing the file and confirm you have it there and spelled the exact same.
Added (2017-05-23, 6:15 AM) --------------------------------------------- for the people who have the same problem i used to have(i fixed it with this !!!!) use http://www.wcreplays.com/forums/showthread.php?t=145532 works like magic.