It's a bit hard too see -- is that font HelveticaNeue?
Hmm .. (HelveticaNeue was a likely candidate for the source of your problem if, and only if, the file was made on a Mac -- its system version of HN is a bit ... messed up ... by Apple.)
Just for clarity, can you check with what software this EPS was made? Open it with a regular text editor, that info should be somewhere in the first lines, usually in a line that starts with "%%Creator:".
If you drop the EPS file on Distiller, is the resulting PDF okay?
%%Creator: Adobe Illustrator(R) 13.0
%ADOBeginClientInjection: DocumentHeader "AI11EPS"
%ADO_BuildNumber: Adobe Illustrator(R) 13.0.1 x420 R agm 4.4379 ct 5.1039
I don't have Distiller installed.
I wonder if the fonts were properly embedded in Illustrator when the first version was saved.
Resaving in Illustrator seems to work? I'd try saving as .ai rather then .eps as a matter of course, too.