I don't think edit-locking is the problem. I drew a picture in Gimp, saved as PNG, opened it in Preview, checked that Adjust Color was available (it was), saved as PDF, checked Adjust Color again, and now it was grayed out!
I also tried saving a PDF document as PostScript (via Print) and getting the resulting .ps file back into Preview, and Adjust Color was grayed out then too. And there is no way to edit-lock a PostScript file, is there?
As far as I can tell, Preview simply does not support Color Adjust for PDF.
The solution I found was to save my postscript as a TIFF file (which can take multiple pages) using the same resolution as I scanned it in. Then I could adjust color and finally save as PDF again. However, I found that color adjustments only worked for one page at a time, even though I selected all of them. I think it's a general command thing for TIFF: cropping also works for only one page at a time in the TIFF file when I do exactly the same thing that works for all pages in PDF. No big deal for me in this case, because I only had four pages, but I would like to know if there is a way to color adjust all the pages at once. Of course, I suppose you can do it with ImageMagick or something like that.