Here are a couple more scripts for toggling shuffle in the latest iTunes. The first one toggles it via the dock:
tell application "System Events" to tell UI element "iTunes" of list 1 of process "Dock"
if not (exists) then return
perform action "AXShowMenu"
click menu item "Shuffle" of menu 1
end tell
You can watch the dock icon menu appear when that one executes.
This second one toggles it invisibly, via the menu:
tell application "System Events"
tell application process "iTunes"
tell menu 1 of menu item "Shuffle" of menu "Controls" of menu bar 1
if (value of attribute "AXMenuItemMarkChar" of item 1 of menu items as string) = "✓" then
click menu item 2
else
click menu item 1
end if
end tell
end tell
end tell
I made this script by modifying what people have written so far, and customizing it to the more recent iTunes menu interface.