Cybermonkey: I've run into this myself quite a few times. Try open the image in gimp or something and fiddle a bit with the compression options when you export. This usually fixes things for reasons I don't fully understand...

(Though reading your suspicion I guess it might be because GIMP adds an alpha channel during the export? )