Wie sind deine Titel getaggt mit welcher Version? Meine mit ID3v2.3 und hat mit dem iPod Classic Gen 6 mit 160GB keinerlei Probleme. Allerdings dauert das immer nen Tick bis sie angezeigt werden.
v2.4 mit UTF-8 kapieren die wenigsten Systeme bisher. Also prüf mal deine ID-Tag-Versionen und evtl. mußt umtaggen...
Das müsste man doch eigentlich in den Eigenschaften / Details des jeweiligen Songs erkennen können.
Früher war alles besser... zum Beispiel gestern: Da war noch Wochenende. 
Dann muß ich ehrlich gesagt passen....v2.3 ist die stabilste Version der Tags und am weitesten verbreitet.
Da es aber ja grundsätzlich zu gehen scheint, kann man nur empfehlen den iPod mal komplett leer zu räumen und neu via iTunes zu befüllen, um die Ordnerstruktur sauber abzulegen. Evtl. liegts daran - wie gesagt ich habe keinerlei Coverprobleme und mache auch nichts anderes als du. Da aber eine rotierende Festplatte im iPod ist, dauert es halt immer eine Gedenksekunde, bis das Cover angezeigt wird.
btw - du hast nen Lightning Anschluss in deinem iPod Classic????