If you look up solutions for this problem in the internet, you can find many posts about it and I tried a couple of them without success. The solution that worked for me is nowhere in the internet and I though I should share it here for more people to make use of it.
If you are one of these people who don’t care about figures quality and would just export Matlab figures into JPEG or PNG or whatever and put it in your paper then, congrats. Your figures does not have fonts to embed or anything to worry about. But this solution below is not for you.
However, people embedding figures with EPS format or any vector format would face this problem and I assume you are facing it right now.