I was able to fix my issue, for now, by
- Making sure the playlists were still in iTunes and set as I wanted
- Backing up the iPhone VIA USB to iTunes
- Doing a restore of the iPhone from the backup I just made in iTunes
However, now I have to go and grab "from the cloud" all the songs that were removed from the phone backup.
At least for now I am back up.