Connect your iPod to your computer and launch iTunes.
Select the iPod under Devices left side of the iTunes window in the source list.
Click Summary from the menu.
At the bottom of the iTunes window you will see how much free space is available.
If it's less than 500 MBs... you need to delete content in order to free up storage space.
Apps, music, video, photos, etc.