Well, what we saw in TOS wasn't a green ship, and what we saw in TMP wasn't a green ship... both were a nice, steel-looking grey tone.
Okay, the MODELS may have been painted with a hint of green, but the models are there to look right on-screen.
It's sort of like how actors and TV personalities wear makeup when being filmed. They do this to look "normal" on-screen, because if they didn't wear it they'd look odd. But if you see them in-person, under normal lighting, with that makeup on, well... it's pretty creepy.
The "green tint" from TOS and TMP was sort of like that, as far as I'm concerned.
However, we did get nice olive-drab ships with ST-III and on. Well, the BOP makes sense, since it's a landable craft... maybe this was intended to be a form of camouflage (in combo with the cloak)?
But there's another potential answer. Maybe Klingon eyes don't work quite like our eyes do? Maybe what looks odd to us is what's natural to them... and they feel the same way in a "human-friendly" environment as we would in theirs.
I know this isn't exactly what we've seen on-screen... but imagine that the Klingon sun were red, rather than "pale yellow" as ours is. You'd fully expect that their eyes would be most responsive in the red range. They might even have that as the CENTER of their visual range, and the higher frequencies which we see might not even be in their visual range at all!
Now... if you look at it that way... shift our visual spectrum so "red" is roughly where yellow is now... you'd basically have slightly yellow (but mostly "white") lights, with a black hull, as the Klingon eye would perceive it.
Just a thought...
