I was able to resolve this by un-pairing and re-pairing my phone. (iPhone 6+). I think I did this from my phone by "forgetting" or deleting the UConnect connection, and then having UConnect start the re-pair. I did this a few days ago and the 3-4 times I have tried since then, Pandora and iHeart Radio are working fine again. (Though if it starts happening again and I need to re-do the process, I will not be shocked).
