For what it's worth, I think that Illy complains when trying to embed a protected font when saving as PDF. This is probably a case of the font failing to embed correctly due to font naming conventions or something, not due to a no-embed flag in the font. When you re-post, you may want to go into some detail on exactly how you "moved" your design from Illy to Acrobat - via a save-as, perhaps? Or some other method?
Also, I think that even when you've embedded the font, you have to go and manually tweak the properties of the field in Acrobat to use your embedded font.
The issue is very simple.
All Adobe software – including InDesign, Illustrator, Photoshop, and Acrobat – respects the embedding privilege flags inside of fonts.
If the font you legally licensed and downloaded has a EULA (end user license agreement) that permits embedding of fonts in PDF files and such embedding flags inside the font prohibit embedding, then your issue is with the font foundry that licensed the font to you, not with Adobe's software. Contact the font foundry for a fixed version of the font.
Note however, that just because you have licensed a font, it doesn't mean that the license includes the ability to embed the font in PDF files, EPS files, PostScript files, etc. And even if it does permit such embedding, the license may also require you to pay a royalty for each PDF file you distribute with such fonts embedded! You really must read those End User License Agreements very carefully.
For the record, all fonts licensed by Adobe permit embedding in PDF, EPS, and PostScript for at least Preview and Print purposes (i.e., viewing and printing the PDF file) with no subsequent royalty payments required for distribution of such PDF, EPS, or PostScript files with the embedded fonts.