Well i can tell youthis, I have done the same thing a couple times. Here is what is happening. *when ever… and i mean when ever, you send a print file to a print EXPAND YOUR FONTS* I learned this from an old pro. The old versions on Illustrator where very painful about this. i always expand any thing that has a style, effect or a font just to be safe…
As for the font thing. here is the reason the printer cant find the fonts and cant see the extensions. your mac… doesn’t uses extensions. a PC…. Stupid PC does…. basicly to stop this from happening you need to copy out the missing fonts and add a .tff or what ever the file type is to the end of your mac file. this might work. i have still had problems with them. Due to the font licensing and what not. if you have an open type font, then you are in the gold and just add the extension and it will work on both mac and pc systems. Open type fonts are the way to go… get them if you can at all cost… saves you time and money.
As for the font changing problem… all i can say is i hope you have a back up or a PDF you can look at for a road map to what you did. I like to print a home proof to check every thing before i send it.. make sure im happy with colors and what not. if the fonts are still giving you problems i would copy and the art layers that are still working into a new file and just rebuild the type layers. I know it sucks but some times you have to suck it up and do it the hard way. just do some testing to see if a new file has the same problems if it does just post back to my answer and i will try to help. ooh yea … one other thing. I would also try restarting… It is an old PC trick.. some times it helps…
Cheers
Lowtech