I’m aware I can personally rebuild each playlist, but I’d much rather solve the issue.
I've encountered what you are going through before and did the following to get it working again, using the Amazon Music software/app on my Windows PC:
1) access your playlists to ensure they're still there
2) rename the playlist (right click) to something else
3) try telling Alexa to play the renamed playlist
4) once tested working, rename it back to the original name
5) do this for each playlist that Alexa is unable to see
These steps worked for me, hope it works for u too.