Have also had this problem with my PC, so not necessarily confined to phones with android.
I had this same exact problem and it was driving me absolutely crazy. Anyways, I'm going to take a wild guess that you use Google Listen to manage your podcasts (hopefully). That's the problem. There's a bug in that software apparently. I uninstalled Google Listen and now I can listen to music with no pausing. Changed my life. Good luck!