Hrmmm. That is strange.

I do know that iTunes prefers album art to be on the smaller side. I generally use PNG images as close to 200 x 200 as possible.

If you want, I can try to work with one of the files you're having trouble with and see if it has the same behavior on my iPod.