I was intrigued by your problem and looked around for an answer. There was a bunch of references to this problem from 2010, but nothing new from this year.
Then it was a bug that occured when you tried to watch a replay on a map that you had never played before. As you added the information that you also have trouble to watch replays of games which you just played the description doesn't match though. Adding the information that other people can watch your replays it is to conclude that your problem is specific to your computer.
Perhaps you can think back whether you have made any changes to your system just before the problem occured. Perhaps you installed some new software that messed with your starcraft2 setup in some unexpected way, or got a new anti-virus software or similar. Perhaps there was some change with your (windows?) user account lately?
If there are no such leads I would try chobok's suggestions from the question comments: Look whether your replays are still stored in the correct place with the correct permissions and lastly try re-installing the game if nothing else helps.