If re-syncing does not help, I can think of two other ideas:
1)
Reset the iPod touch by holding down Sleep/Wake and Home buttons together for at least ten seconds, until the Apple logo appears.
2) More drastically (not too bad though!),
you could try the Restore option from within iTunes. You will reset it to being essentially a new, blank iPod and you will need to re-sync everything, but it does sometimes sort out problems.
Let me know how you get on at the Apple Store. Good luck!