A wild guess here, but what file type is the art in iTunes? Is it something we know is supported on the iPod like .jpg, or is it something weird like .png or .ico or something?
Personally, if it's just this one album, I'd replace the art in iTunes with a new image, then when you have your iPod mounted next UNcheck "album art on iPod" and let it erase all your art. Once that's done REcheck "album art on iPod" to make sure it's grabbing the new image.