Are you jailbroken?
My friend who owns an iPod touch jailbroke and when he went to sync all his apps back, half of them were already on the Touch just not showing up on his springboard. So I had to SSH into his Touch and delete all his Applications, then get him to re-sync them