There is no good solution within Acrobat Pro itself.  However, you CAN do the edit if you also have Adobe Illustrator installed.

Open your PDF document in Acrobat Pro.  Instead of using TouchUp Text Tool, use the TouchUp Object Tool.  Select the line of text you wish to alter, right click and choose Edit Object.

Your line of text should open up in Illustrator.  Illustrator will use a substitute font, letting you edit at will.  NOTE: you will NOT be able to save your change in the original font.  Good news is that Illustrator has a large number of fonts to choose from and you will most likely find one that is very close to the original - good enough for quick edit purposes.

Save your change and exit Illustrator.  Your change should be reflected by Adobe Acrobat Pro.  Another benefit is that your changed text is now TouchUp Text editable from within Acrobat Pro.

SeanCole's solution didn't work for me. When in Illustrator, the characteres appear as garbled icons and cannot the switched back to any font.

Any other ideas?

Correction: Acrobat 6 instead of 2006

I was getting this error a lot with PDFs generated by the Adobe PDF printer device.

After some thought, I looked at the "Printing Preferences" for the PDF printer and noticed an option "Rely on system fonts only; do not use document fonts.".  Obviously that prevents embedding of fonts (which reduces file size), but also causes the fonts to be made unique, ie. "Arial+0" rather than "Arial", etc.  This prevents the editing, regardless of whether the font is installed or not.  Unchecking that option and reprinting the document solved that problem.  The TouchUp Tool worked thereafter.

Obviously that solution only applies to PDFs created from that source, but might point people in the right direction for related issues.