Well, I figured out my own answer by the art of adding one optimization feature at a time.
This option, under Discard User Data, is the one that kills the index links:
Discard all comments, forms & multimedia.
Thanks Adobe for your highly descriptive option name.
This helped, but I noticed (in my case) on CS4 for Mac, that this only saved a few hyperlinks. To be specific it only saved the hyperlinks for text that matched the link.
For example, if I wrote, "click here" and then added a link to that phrase, that disappears even with that option checked when I try to open it with Preview.app on a Mac. This was also true if I added a link to an image, that would disappear even with that option unchecked during the optimize pdf part.
Any other suggestions for which other puzzle piece I need to remove to make all hyperlinks work after an optimization?
Anyone find the solution to the loss of internal hyperlinks that have been re-named?