Sounds like they didn't embed the fonts when they wrote the eps. You can't do anything to change that except have them rewrite it again for you. When you view it in Acrobat does it match hard copy they have provided? If you don't have a hard copy generated from their
computer to show you what it is supposed to look like, there's a possibility that when you view the document on your
computer the fonts are defaulted and not matching the original. Just had this happen on a job that I used an LHF font on and forgot to change to outlines. Customer was viewing a defaulted pdf in Reader everytime without knowing it and called to complain when the ad ran with a different font (which was the correct font according to the design).
Another possibility if hard copy matches is the presence of what I call ghost fonts. Usually a space bar or in illustrator a type point that you can't. Let it open in Illustrator and then do a replace/find on the missing fonts to see exactly where they are.