I'm not sure if anyone is still having trouble with this, but I found a way to create a playlist that will shuffle the podcasts and music.

1. Make sure that the option to sync podcasts directly onto the iPod is chosen.
1a. To do this, click on the "iPod" tab in the top right corner, then the "podcast" section, and then click on the box that allows for syncing. Click on "done" when finished.

2. Click on "file" in the top left corner, "new" and "smart playlist" that matches the rule of "plays is 0."

3. Your music and podcasts that have NOT been played should come up in this playlist now!
3a. If you want to add ALL of your music, go to the music tab, highlight everything, right click, and then click on "reset plays"

4. If you try to play it on your iPod and shuffle at this point, it may separate the podcasts and music into 2 different playlists for some reason. This was very frustrating.

5. To overcome this, highlight everything in the playlist on the computer. Right click, "get info" and then "options."

6. If "skip when shuffling" is clicked, UN-CLICK it. This should allow for podcasts to show up on the iPod with the music when shuffling.

7. Sync iPod as usual.

You can download and delete podcasts from it's own tab in iTunes, and it should directly affect this playlist. I suppose this upgrade is easier in the long run, but it was a pain to figure out.