You get this problem when the option 'Sync Music - Selected playlists' is being used to sync your iPod. If the playlist selected is deleted from iTunes the iPod no longer has a location to sync from and you get an error. (Syncing selected playlists by the way is a useful setting to use when the iPod is smaller than the iTunes library). However you can make a new one or make use of an existing one.
Open iTunes and create a playlist to update your iPod from, call it -My iPod for example (the dash will position it at the top of the playlists in Sources). You can make it a smart playlist that picks the songs for you or just a normal one and drag whatever content you want to have into the playlist. If you are making a smart playlist limit it to just less than the size of your iPod (for example 3700MB for a 4G iPod Nano. Now connect your iPod and when it appears in the Source list click on the iPod icon to bring up the preference tabs in the main pane. Go to the Music tab and choose Sync Music and the Selected playlists radio button. Choose the playlist you just made from the selection and click Apply. You can also sync from any existing playlists by choosing the same setting, you just need to make sure that the size of the playlists don't exceed the capacity of your iPod:
How to create a Smart Playlist with iTunes
Syncing Music to iPod
To make a random playlist go to File>New Smart Playlist.
Uncheck "Match the following rule"
Check "Limit to" put "3700" in the number box, choose "MB" from the first list box, choose "Random" from the next list box. Check "Live Updating"
When you want to change the selection in the smart playlist just delete everything in it and it will add a new selection. When you want to change the normal playlist just delete out what you don't want and drag in a new selection.
Alternatively if you don't want to automatically sync music to your iPod you can change your update setting to "manually manage music and videos". If you want to manage it manually then connect your iPod and click on the iPod icon in the iTunes source list to bring up the preference tabs in the main pane. In the Summary tab check the box "manually manage music and videos" and click Apply:
Managing content manually on iPod and iPhone
Syncing Music to iPod
Something to remember about using an iPod in manual mode is that the "Do Not Disconnect" message will remain on the display until you physically eject the device. In that case use the Safely Remove Hardware icon in the Windows system tray on the desktop and check this link for alternative methods:
Safely Disconnect IPod