Editing a PDF in Illustrator is a resort-after-the-last-resort maneuver. You should try to get hold of the original file and edit that. But you probably know that already and have either ruled out asking for it or been told it is unavailable, so here we are.
Your best bet for editing the colours is to do it in Acrobat, not Illustrator. Use Acrobat’s Advanced > Print Production > Output Preview command, you can convert any spot colours to process. Probably the colours are used in some objects that Illustrator cannot interpret into fully editable artwork. This often happens with areas where transparency was flattened when the PDF was made.
Can you change color there? I thought it was only in the Convert Colors window...
On a side note, if you still get anything odd there, you can try to import the PDF to ID and then change the color. Ive gotten different results with each method.
You can also try this from Illustrator's print dialog there is the option to convert spot colors to process and you can use the option to print to a Adobe postscript file which can be opened in Illustrator or distilled. I t looks like it does a very good job on the conversion.