Have you tried resetting it using the menu and `nipple` button? (You hold both down for 5 seconds).
I had the `corrupted` message recently on my ipod shuffle and had to download a program to resolve it. However, yours may just be a case of formatting it and then doing a restore.
Check out Apple`s forums - they`re normally quite good.