Go to the main menu—Disconnect your iPod from your computer, then press the Menu button until the menu title says "iPod," regardless of the language displayed. This means you are at the main menu.
Select your language.
If you have an iPod nano or Fifth Generation iPod (iPod with video):
Scroll down to the last menu option but don't select it.
Scroll up one menu item. This should be Settings.
Press the Center (Select) button. This takes you to the Settings menu.
Scroll down to the last menu option but don't select it; in English, this is the "Reset All Settings" option.
Scroll up to the third menu item from the bottom one. This should be Language.
Press the Center button to select Language.
Select your preferred language from the list.
http://support.apple.com/kb/ht1824