Q: Have they resolved the playlist shuffle issue for the new version of itunes?

You are trying to play a playlist in iTunes using shuffle?  Select the playlist in iTunes.  Above the list, to the right of the playlist name, there is an icon that looks like two arrows crossing (the shuffle symbol).  Click that icon to shuffle the playlist. 

Or, are you trying to play a playlist on your iPod in shuffle mode?  Which model iPod nano do you have?  Does it have a clickwheel or a touchscreen?

In iTunes, "shuffling" is an option for playing a playlist.  The actual playlist order is not changed when you shuffle the playlist for playback. On a playlist, you can see the playlist order by clicking on the column heading area above the left-most column of the list (the column with sequential numbers).  That sorts the playlist in playlist order.  You can manually move songs around on the list (by dragging the songs) to change the playlist order, but there is no command to "shuffle" the actual playlist order.  There is really no need.

On the iPod, "shuffling" is also an option for playing a playlist.  You did not answer my question about which type of nano you have, but assuming it's a 6th or 7th gen nano (with a touch screen)...  When you are playing a playlist, on the Now Playing screen, there is button with a symbol that looks like two arrows crossing (the shuffle symbol).  Tap that button, and the current list is played in shuffle mode.  (You may need to tap or swipe the Now Playing screen to show that shuffle button.)

So, I don't know why you would need to shuffle the playlist order of a list before you sync.  You can just shuffle the playlist while you play songs from the playlist on the iPod.

For an iPod that has click wheel, the shuffle setting is on the iPod's Settings screen (on the iPod).   There is a setting called shuffle.  Set it to Songs.  Select a playlist you want to play, without going into it.  Press the Play button and the playlist should shuffle its songs for playback.

NOTE:  If you go into the playlist, you can select the first song to play.  After that first song, the subsequent songs will be shuffled.

Using the shuffle function in itunes and on the ipod itself works great and all, but there are a few third party components that don't have a shuffle feature. The treadmills at the gym I go to do not offer a shuffle feature so having a playlist that is already shuffled, like itunes used to be able to do, came in handy. Any easy way to randomize a playlist prior to sync?

If you're still looking for a way, this might work for you.

In iTunes create a new Smart Playlist.  This Smart Playlist is going to be the shuffled version of the playlist you want to have on your iPod.

In the Smart Playlist's setup/edit window, check the box for Match the following rule.  Set the one rule to be

Playlist - is - [select name of the playlist you want to use]

You do not need to add any other rules, but check the box and set up the option to

Limit to [number] items selected by random

Enter a number that is more than the number of songs on that playlist.  So, if you have a few hundred songs on the playlist, you can enter 1000.

Check the box for Live updating.

Click OK.  The new Smart Playlist should contain the same songs as the playlist you selected, but with the playlist order randomized (compared to the original playlist), because you told the Smart Playlist to select items from an existing playlist randomly.  Since the number of items limit is higher than the actual number of items on the playlist, you should get every song.  Sync this Smart Playlist to the iPod.

This worked for me!  Thank you!!  You've made my day

I have just purchased an ipod touch Version 7.0.4, Model MD717BT/A. This is an ipod touch 5 I believe. Looking at the proposed solutions to the shuffle within a playlist, I have tried this, but no luck. I have gone to the 'now playing' display and tapped the album work on the track. There are no additional small icons displayed, does not change colour around the edges etc, so does anyone know the answer for this ipod touch model please?

An iPod touch is not an iPod nano.  It's a mobile computer like an iPhone and runs iOS.

This is the user manual for an iPod touch running iOS 7.  See page 52.

http://manuals.info.apple.com/MANUALS/1000/MA1596/en_US/ipod_touch_user_guide.pd f

This Apple web page has links to resources for the iPod touch

http://www.apple.com/support/ipodtouch/

What if I have a 120GB ipod classic? I want to set each playlist in a random order in itunes before I drag it into my ipod, instead of having 20 songs from the same artist consecutively. When I had the old itunes I would do the following: Create "Rock Mix 1" and add music to it. Then I'd turn on shuffle, which COMPLETELY randomized the music list. Then I create a new playlist called "Rock Mix". Then I highlighted all the songs (in the randomized order) from "Rock Mix 1" and drug them over to playlist "Rock Mix", after which the playlist was SAVED in the random order. Then I deleted the old "Rock Mix 1" playlist and drug the new playlist over to my ipod. However, the new itunes does not actually shuffle the songs in the playlists anymore, it's for playback in itunes only. I tried the "Smart Playlist" option above (with the "random" option selected), but all that did was flip the playlist, so that the bottom was at the top. It doesn't actually scramble all the songs, which is what I'm trying to do. I COULD spend an hour manually dragging all the songs in my playlist to a random order, but that is a very tedious task that I'd rather avoid, if possible. Any suggestions for this?

In your case, why do you need the playlist to have a random order?  Why can't you just have the iPod play the playlist in random (shuffled) order?