All in iTunes:
1) Find the album this affects. Right-click one of the tracks and click 'get info'. Click the artwork tab. Hopefully it should show the artwork. If not, procede to the next track, until you find the one with the artwork (sometimes, it just adds artwork to one track on the album).
2) Drag this picture to the desktop. (I'm on a Mac and you can do this, I assume it's the same with Windows. If not, then use Google Images to find a good quality image of the album, and save that to your desktop).
3) Now press cancel in this dialog box, and then highlight all tracks on the album. Right click and 'get info', showing you the info for all the tracks at once. There's a little thumbnail area for artwork. Drag your image that's on the desktop back into this thumbnail area. Click ok.
4) After a few seconds, it'll apply the artwork to all tracks. Sync your iPod and see if it works!