als er in der Liste anzeigt? Ich habe die Lieder schon in iTunes (4) umsortiert, aber das hilft nix. Wenn z.B. ich alle Lieder der vier David Bowie Alben anzeigen lasse, stimmt die Reihenfolge, sobald ich sie anspiele sind sie komplett durcheinander (also nicht mehr nach Alben oder Titel sortiert).
Mit der alten Firmware bzw. iTunes 3 war das noch in Ordnung

Ändere einfach mal die Abspielreihenfolge von vorvärts auf Rückwärts in deiner iTunes Liste (über der Nummerrierung auf die Taste mit dem Pfeil klicken) und dann nochmal. Beim nächsten Anschluss des iPods sollte sich das geben. Wenn nicht, dann ist es ein neues Phänomen.

das habe ich schon mehrmals versucht, hilft aber nicht.

Habe die gleiche Erfahrung (iPod 1. Generation, neueste Firmware, iTunes4) gemacht zuerst mit der Doppel-CD Dream Dance 27, die ich nach Rippen in AAC und sortieren nach CD-Nummer (1 von 2, 2 von 2) und Tracknummer in eine eigene Playlist einsortierte. Nach übertragen der Playlist auf den iPod mischte dieser die Tracks selbständig beim Abspielen...
Hingegen verhielt er sich bei der nächsten Doppel-CD (Space Night Vol.9) anders. Diese rippte und sortierte ich auf die gleiche Art, doch hier spielt der iPod alle Titel in der richtigen Reihenfolge (d.h. Titel 1 von CD1, ..., Titel 10 von CD2) ab.
Ich vermute, dass es evtl. an der Sortierfunktion in iTunes liegt (Playlist?).

inzwischen habe ich eine Ursache herausgefunden:
aus irgendeinem Grund war eingestellt, daß die Titel eines Interpreten in zufälliger Reihenfolge abgespielt werden. Bewusst habe ich das aber nicht eingestellt, möglicherweise ist das Update oder iTunes schuld daran.