then add your font to the list that gets embedded. then you have to choose all the kinds of formatting you've applied to that font as well. like bold, italic, regular. and so on.
if you do all that you shouldn't have any problems. it is a little annoying, as in previous versions like cs3 i never had to do any of this, i just embedded a-z, A-Z and 0-9. and it would work. but i guess theres more to it now. :P