iTunes & iPod have slightly different ways of working with the same data which can cause problems. I don't have access to an iPod Touch or iPhone but similar problems occur with the Classic line. See my previous post on
Grouping Tracks Into Albums, in particular the topic Missing Artist or Album not with others by same artist. The lastest upgrade may have made the Touch more sensitive to any minor spelling inconsistencies in either the Artist or Sort Artist fields which don't reveal themselves in iTunes. Like the "Greatest Hits" bug which confuses all albums with the same title, an inconsistency could cause two instances of the artist to be listed, and then connect all tracks to both copies.
tt2