I have had similar issues on my phone (Galaxy S9) since the Amazon Music HD service launched and am starting to suspect it may have to do with some tracks that Media Monkey imported on my phone (some of these are MP3s I have purchased from Amazon). I emailed Amazon when the new service launched about the issue but they wanted to troubleshoot live. I just spent 5 hours on the phone with them regarding AMZL shipping/delivery issues over the last 2 weeks so I think I am done talking to Amazon CS for a while. For now, I am slowly recreating my playlists on Amazon to see if removing the music from my phone will help fix the issue. I am also having to constantly logout and log back in because songs I add to my playlist are not showing up until I do so (or the app tells me that a song I have never added before is already on my playlist and clicking "Refresh My Music" or clearing cache does nothing).
I agree this is a real pain to deal with and given how buggy the app is, I will probably go back to buying CDs when my trial is up unless the service improves substantially.