It’s hard to tell without seeing it, but I’d guess that the text is being rasterized during the PDF creation and the resolution is set too low.
A couple of things:
1) Outlined text or text turned to curves will generally print a little ‘heavier’ than still-a-good-old-font text… especially at smaller sizes. However it should still be sharp and crisp as it is vector data and not dependent on resolution. Headlines will be fine; legal fine print not so much.
2) I forget what number two was going to be… Uhm… Oh! The text will still look sharp in Illustrator, because Illustrator is displaying native art objects. But when you convert to PDF, the text can get beat up. Make sure that your ‘Document Raster Effects Settings’ and, if applicable, your transparency flattening settings are approriate for your output.
Good luck!