Well, I havent heard from anyone but have figured it out myself, so I'll explain what happened.
I have two installs of gallery. One worked, the other didn't. One the one install that it worked with, I had downloaded the binaries of netpbm from this site. On the other, it was set to use some that I had compiled. Well, for whatever reason the ones I compiled didn't work, and I still don't know why. The auto-configure of the non-working gallery found netbpm found these others which didnt like greyscale, and used those. I manually edit config.php to point to the ones I had downloaded from gallery, and all is OK.
So, I don't know if there's something special that needs to be done when installing netbpm from themselves, but I guess I (and you) should always use the binaries from gallery if it's possible to avoid pains-in-the-asses.
