I am using Arial Bold in a document and when I go to Print to a Postscript file (how our printer wants our pages exported) I'm getting an error in Acrobat. I check the page in Acrobat with our printers setting and I am getting an error message saying the font isn't embedded. I am doing this exact process with the exact document on another computer and I am not having an issue.
If you create a PDF, avoid postscript, no EPS, no printing to PDF or .ps, export PDF! Ignore the printer's advice.
If the font's licence allows embedding, PDF export will embed it. If not, you have to choose a different font.