iPhone shows album art but iPod classic doesn't
Might have to do with how artwork is stored. iTunes can store it in the mp3/aac/whatever music file or in a separate database. 

I noticed when exporting often the art is not included. A way to force iTunes to include the artwork in the file is to edit the file info in iTunes - like e.g. add a comment. Then the tag is rewritten with artwork also included.