I resolved this different ways for my iPad vs. my iPhone.
For my iPad, I went into the Music preferences, turned off Show All Music first, then turned off iTunes Match. Once that was done, I went into the Music app, selected Genres, then held down a cover until I got the wiggle and deleted all of the genres (essentially, all of the music that was physically on the iPad).
I restarted my iPad, turned iTunes Match back on, and the data seemed to clean itself up.
Unfortunately, you can't delete your local music from your iPhone in the same way (and even if you do, the database is still all messed up).
The only solution I was able to find was to Backup my iPhone, do a complete Restore, then Sync all of my data back onto my iPhone. It all took about an hour (most of which was syncing) to complete, from start to finish. I haven't had any regressions of my music back to the buggy playlists ever since.
----
Interesting side-note:
On my iPhone, the only way I could figure out how to manually delete the music in the largest possible quantities was to delete everything Artist by Artist (i.e., there was a larger quantity of albums and tracks than there was for artists).
I had 2 artists in the "123" section (at the end), then 1 artist in the "Z" section, then 3 artists in the "Y" section (and so on). When I deleted the very last artist in the list, all of the entries shifted down by one while the sections contained the same amount of entries (i.e. "123" had a numeric artist and the Z artist; "Z" had one of the Y artists; "Y" had the other two Y artists and a W artist it had pulled down into itself).
Despite what various Apple Geniuses or tech support people say, this is absolutely a bona fide bug.