Geniice told me on IRC, if I understand correctly, that you might change a copyrighted image (fair use or not) if it is a very small part of the original, like for a parody (under USA-law). But album covers are not part of this.
Not quite. Those were the first examples I could come up with. It is not say there are not others but since en.wikipedia does not allow modification of fair use images it isn't a subject I worry about very much.