Before I begin, this is for the newer custom_certificate plugin and not the old certificate plugin.
This post is for those that have downloaded their certificate only to find something like this:
https://moodle.org/mod/forum/discuss.php?d=361331
Why is this happening?
The custom certificate plugin uses the TCPDF PHP library to create PDF's, and the TCPDF library has some free to use default fonts that can be provided to custom certificate. This library is great with english characters, but isn't so great with most non-english characters. The issue arises when you use unrecognised characters in your certificate.
To fix the issue, you need to upload a custom font to the library directory. The custom certificate plugin isn't at fault here. How to do this is explained below:
How to fix
Download a font that you are licensed to use. The file downloaded will usually be a TTF file.
Then, find a tool online that can convert that TTF file into the three files TCPDF uses (usually a PHP file, .z and ctg.z). I used this website: http://fonts.snm-portal.com/ to do the conversion.
When you have all of them, upload them to the moodle directory under lib/tcpdf/fonts and then you should see your new font appear in the custom certificate plugin on next refresh!
It really is that easy.