It really needn't be that difficult, and there really is no need to make a playlist to do this.
Step 1: Not even really a step. Not even necessary if you use the Database, just make sure recursively insert directories is set to on if you use the "Files" browser to do this..
Step 2: You can do this in the database, or the files menu:
Files: If you have a music directory (as in .rockbox/Music/), bring up the context menu on this directory (the manual can help you here, context menu is "long select" on the iPods), choose "Playlist", choose "Insert Shuffled".
Database: Open the Database, bring up the context menu on "Track", select "Playlist", select "Insert Shuffled".
After step 2 (either Database or Files method), your music will begin to play automatically
Step 3: Done.