plug your iPod into iTunes. Let it update, automatically. Not manually.
Wait until this is complete, then delete all the On-The-Go playlists inside iTunes (not within the iPod, which you shouldn't be able to do anyways, if you leave it to update automatically).
Once you've done this, and made sure you've deleted them all, update your iPod again, automatically. Click on it and right-click (on windows at least) within iTunes, and choose "Update Songs On #iPod Name#".
That should do it.