It's quite possible the font is contained within the PDF itself, but in such a way that you can't add new text that uses it.
PDFs can carry fonts within themselves in two ways:
- Embedding, where a complete copy of the font is added to the PDF
- Subsetting, where only part of the font is contained in the PDF—specifically only the glyphs needed (e.g. if there was only the string 'Hello' in that font, then only the glyphs 'H', 'e', 'l' and 'o' would be subset in the PDF).
Subsetting is much more common, because it takes less space and also makes it harder to recover the font (font vendors really want you to buy a copy of the font for yourself). However, it's almost impossible to add new text using a subset font (since you possibly don't have all the glyphs you'll need), and as such Acrobat Pro and other tools refuse to let you do it.
In the document properties, it should tell you if a font is embedded or subset. go-meek is right, though: your only option in that case is to use a different font that you have available on your system.