To be absolutely explicit, Acrobat Preflight can only embed fonts into a PDF file in which fonts are referenced but not embedded if all the following are true:
(1) The fonts in question must be installed on the computer on which Acrobat is running. Obviously, if the fonts are not installed, Acrobat Preflight cannot conjure them up! 
(2) The fonts don't need to just match in name, but must substantially match the original referenced font. For example, if the original referenced font was a Type 1 font, a TrueType version of that font will probably not be considered as a suitable font.
(3) Character set and character mapping mismatches. As an example, there are very many versions of Arial over the last 25 years, some with less than 256 distinct character definitions and some of the more recent versions with over 5000 character definitions. If your original document referenced characters that are not available with the version of Arial you have installed or the character mapping is different, the font cannot be embedded.
(4) The font's embedding flags must allow for the font to be embedded in a PDF file. As strange as it may seem, there are fonts licensed (not by Adobe) that don't allow for embedding. If Adobe applications including Acrobat Preflight encounter such fonts, the applications will obey the intent of the font foundry as expressed by the embedding flags and not embed the font in the PDF file, either during PDF file creation or other operations such as Preflight.
- Dov