I think I've found a solution. It's not perfect, but it's pretty close to the old behavior.

My goal:

• Play recently-added songs most often;
• Also include a selection of older songs;
• Play higher rated songs of each set more often;
• Only play un-checked or un-rated songs if they are recent.

I used to be able to accomplish this with 2 playlists. Now I need 11.

To make ratings mean anything, you need one playlist for each rating level, weighted accordingly. I gave 1 through 5 stars the weights of 12%, 16%, 20%, 24% and 28% respectively. I pulled that out of my butt, but it seems sensible. So if you wanted to end up with 250 songs, weighted, you'd need playlists of 30, 40, 50, 60 and 70 songs, respectively. Likewise, 750 songs is 90, 120, 150, 180 and 210.

Create playlists like so:

1. File / New / Smart Playlist: "Shufflable"
   (This one is for the settings common to all sub-playlists.)
   • Kind • is • MPEG audio file
   • Media Kind • is not • Podcast
   • Last Played • not in the last • 7 • days
   • Last Skipped • not in the last • 14 • days
   • Playlist • is not • "Bored with"       ← or whatever
   • Match unchecked items
   • Live updating

2. File / New Folder / "75% Recent, 25% Library"

3. Make the five "25% Library, 250 tracks" sub-playlists inside that folder:
   1. File / New Smart Playlist / Library 30 ★
      • Playlist • is • Shufflable
      • Rating • is • ★
      • Limit to • 30 • items • selected by • random
      • Match only checked items
      • Live updating

   2. File / New Smart Playlist / Library 40 ★★
      • Playlist • is • Shufflable
      • Rating • is • ★★
      • Limit to • 40 • items • selected by • random
      • Match only checked items
      • Live updating

   3. File / New Smart Playlist / Library 50 ★★★
      • Playlist • is • Shufflable
      • Rating • is • ★★★
      • Limit to • 50 • items • selected by • random
      • Match only checked items
      • Live updating

   4. File / New Smart Playlist / Library 60 ★★★★
      • Playlist • is • Shufflable
      • Rating • is • ★★★★
      • Limit to • 60 • items • selected by • random
      • Match only checked items
      • Live updating

   5. File / New Smart Playlist / Library 70 ★★★★★
      • Playlist • is • Shufflable
      • Rating • is • ★★★★★
      • Limit to • 70 • items • selected by • random
      • Match only checked items
      • Live updating

4. Make the five "75% Recent, 750 tracks" sub-playlists inside the same folder:

6. File / New Smart Playlist / Recent 90 ★
   • Playlist • is • Shufflable
   • Rating • is less than • ★★     ← include both ★ and ☆
   • Limit to • 90 • items • selected by • most recently added
   • Match unchecked items         ← include un-checked
   • Live updating

7. File / New Smart Playlist / Recent 120 ★★
   • Playlist • is • Shufflable
   • Rating • is • ★★
   • Limit to • 120 • items • selected by • most recently added
   • Match only checked items
   • Live updating

8. File / New Smart Playlist / Recent 150 ★★★
   • Playlist • is • Shufflable
   • Rating • is • ★★★
   • Limit to • 150 • items • selected by • most recently added
   • Match only checked items
   • Live updating

9. File / New Smart Playlist / Recent 180 ★★★★
   • Playlist • is • Shufflable
   • Rating • is • ★★★★
   • Limit to • 180 • items • selected by • most recently added
   • Match only checked items
   • Live updating

10. File / New Smart Playlist / Recent 210 ★★★★★
    • Playlist • is • Shufflable
    • Rating • is • ★★★★★
    • Limit to • 210 • items • selected by • most recently added
    • Match only checked items
    • Live updating

That's a stupid amount of work, right? Well, you can save yourself some effort with strategic use of "Duplicate Playlist". It would be nice if I could just export an XML file of the playlist rules for you folks to import, but that doesn't work (it exports the current set of tracks instead). And you can't create smart playlists from Applescript either.

And after all that, if you set "Up Next" in the iTunes Mini-Player to the playlist-folder "75% Recent, 25% Library" (by clicking on the magic shuffle dingus), you should have reasonable things happen.

Update: Now here's how it fails.

• Let's say you haven't bought music in a while, or haven't rated too many things with five stars lately. That "Recent 210 ★★★★★" playlist might have a couple hundred tracks in it that aren't really very "recent". You might choose to also limit that playlist (and the other "recent" playlists) to "Date added • in the last • 12 months" to keep only recent-ish highly-rated tracks in it -- but now the carefully-chosen ratios will be out of whack, and your recent five-star songs might actually end up being played less often than your more-numerous recent three-star songs.

• Often, even though the Mini-Player is set to shuffle from the "75% Recent 25% Library" playlist folder, it will play six or ten songs in a row by the same band! All of these tracks are present in the playlist, but with a thousand tracks in the playlist it's statistically impossible for this to happen as often as it does if they were truly being chosen randomly. I have no idea what it's doing. The queued tracks are in non-alphabetical order. The chosen column for sorting in the sub-playlists doesn't seem to affect it, but it's hard to test. It's as if iTunes went out of its way to do the stupidest possible thing.

This is all bullshit, and it sucks.

Previously, previously, previously, previously.