I've had something resembling that, with songs locking up.

Here's how I remember fixing it.

Make a note of which songs are skipping/freezing.
Remove them from iTunes but don't delete them from your hard drive.
Connect the iPod to your PC and it should run a drive diagnostic. (The screen will go blank briefly and a picture of a spinning hard drive with a fuel gauge underneath will appear.) Let this run to completion.

When it's done checking itself, press the Menu button to let it sync up.

Once the update is finished, disconnect the iPod.

Import the songs back into iTunes and re-connect the iPod.

After the iPod syncs up, you should be okay.

To remove a song from iTunes without removing it from your hard drive, click on the song title to highlight it and then from the Edit menu select Clear.

You should be asked if you want to trash the song in addition to removing it from your library.

Click on No at this point and you've got it.