I have had this same problem for years. I think it's more a problem with the OS than any one phone. I started with a Motorola Droid and have since moved to the Samsung Galaxy Nexus. I've also changed head sets twice. Always had this choppy audio problem.
I use my phone while I jog, depending on...