I know this is old, but I have been searching everywhere for a solution.
Problem: Barcode fonts would print to the printer, but would not embed in PDF. I tried reinstalling the fonts and the PDF creator, and upgrading Adobe Reader. The fonts were licensed. I just could not get them to embed in a PDF no matter what I (thought) I tried.
Solution (for me): Uninstall all the troublesome fonts first! Make the Windows User (this is important) who will be using the embed feature an administrator on the PC. Usually just log in as Domain admin, change the user account type to administrator and log off. Log back in and make sure the fonts are indeed deleted from the admin folder.
Reinstall all the troublesome fonts. Now try to create the PDF. Demote the user.
Why this worked for me is the fonts were usable in many programs but since they were not installed as administrator, I could not get the licensing to function - which PDF's need in order to embed.
I hope this works for someone else.