Why don't you deactivate Font Explorer and open the fonts you need that are in the document? It sounds more like a Font Explorer problem as you're describing.
There's no way to choose substitute fonts in Acrobat if you don't have the needed font already installed and open.
No, the conflicting Times font is not handled by Font Explorer, it's installed by the Mac OSX system (which, very unhelpfully, installs its own versions of Times and Helvetica, under those names, which often don't play well with the rest of the universe's Times and Helveticas, say Adobe's and Microsoft's. I have the other versions of Times and Helvetica available in Font Explorer, but unchecked so that I don't have font ambiguities.
I did try overriding a Font Explorer warning and opening BOTH versions of Times, and that seems to work as far as previewing the PDF and placing without having to check 257 dialog boxes. I doubt it's recommended, though; but fortunately I'm not doing a lot of work on these files, so if the application goes down in flames I won't have lost much time...
For what you're doing, I don't anything terrible will happen to keep both versions of Times Roman open at the same time. When you're through with the project just close the extra copy
If the fonts are not embedded, Acrobat requires the actual version of the font open and installed or it does font substitution automatically, as you saw.
You can safely removed the system times and helvetica.
If you use iCal, Mail and a few other Apple programs that use badges on the dock icon you will get a substitute font on the icon, but having another helvetica will fix that. You need 1 Helvetica of any type or Photoshop will not launch.
The only fonts you NEED in OS X are Lucida Grand (used in menus), Last Resort, and Keyboard. The rest can be deleted. Apple says you have to keep Kana, but if you aren't working in any Asian languages you can remove it without system instability. To be safe and follow Apple's guidelines you can keep it.
Helvetica Neue rather than Helvetica on the badge icons. I generally suggest people install their preferred Helvetica Neue into their /System/Library/Fonts/
You'll see some of the support community say to absolutely never ever ever ever ever remove the fonts in Protected fonts, but that's hogwash, especially in the case of Helv and Times. Not likely you'll care about Geneva or Monaco or any other font named after a city being in conflict, but equally unlikely you'll go for a nice Geneva font for your layout or any Helvetica clone when you actually have Helvetica.