I'm afraid I have no solutions to help you, I can only say I have experienced that error message (along with many more), only my ipod has 10 gig free.
i have also had my ipod for over a year now and am only just experiencing problems ... it's starting to feel like a time released virues ... well ... only when I'm at my most paranoid.
