I also have this issue on my Echo 4th Gen.
I do have Pi-Hole on my network, but I also have Pandora Plus subscription, so there shouldn't be ads in the first place? I'm not going to add exceptions to my Pi-Hole; I purchased the subscription to get rid of ads.
My Alexa just started doing the same thing! I’ve played Pandora on it for years, with Ads. No issues at all until the last couple of weeks. I have no ad blocker and it plays Amazon music with ZERO issues. I don’t want Amazon music. I want to play Pandora but it’s so frustrating! My husband has no ads on his Pandora but it still stops playing. It’s nice to know that many of us have the same issue but would love for this to be fixed.
I been having the issue with my new device but it never happen with my old device. I have tired all these steps but they seem to not work. This issue started 2 months ago and it's only the smooth jazz station that keeps getting disconnect not other issue from any other station on my account.