Does Acrobat display the error message when you open the document?
Which version of Acrobat are you using (including all sub versions e.g. 6.0.5)?
Have you tried to open the file in Adobe Reader 7 or a later version of the full Acrobat?
When you open the file with "use local fonts", and select the document information panel, what information is displayed for these fonts?
When you export the PDF file, can you specify a PDF compatibility level (e.g. PDF 1.4/Acrobat 5, ...)? What is it set to? Have you tried to go with a lower version number?