New playlists created in iTunes or the Nano will not shuffle

The first thing to check is whether the other songs will play in normal mode. If they do, that suggests that the songs have been set to skip un shuffling. This is an option in iTunes.

If this is the case, check the songs in your iTunes Library:

• select a song and right-click/Song Info/Options>Skip when shuffling. If there is a tick in the Skip when shuffling box (a check mark), then the option is turned on and that is why it won't play in shuffle mode. Turn the tick off and sync the iPod again (to get that revision onto the iPod)
• to change several songs at once, select them all and right-click/Get Info. Click on Edit Items and then the Options pane. Again, make sure there is a tick in the box

Important information if you say "check mark". The following indication is not the check mark:

That indication tells you that some, but not all, of your selection is ticked. Click on the box until the tick appears, as shown below:

I'm pleased you managed to sort it out, despite my somewhat dubious instructions!

If they do, that suggests that the songs have been set to skip un shuffling.

Should read as: If they do, that suggests that the songs have been set to skip when shuffling.

Again, make sure there is a tick in the box

Should read as: Again, make sure there is no tick in the box, that the box is empty.

Click on the box until the tick appears, as shown below:

Should read as: Click on the box until the tick appears, as shown below and then click the box again to turn the tick off.

Other than that, my post was "perfect". (If only that were true.)

Well done.

the fiend