WOW, HTC STILL HASN'T FIXED THIS ISSUE!!!?!?!?
OK, so I had an Evo 3D (yes that's 4 generations ago) There was a known issues which sounds like the same thing that happening here.
The phone recognizes whether you plug in a headset with a mic and button or headphones without a mic and button. You can tell because the icon shown in the status bar is different. (One just looks like headphones, and the other looks like headphone with a mic on one side.) Anyway, SOMETIMES if you plug in headphones without a mic, the phone recognizes it incorrectly and thinks it has a mic and button (it will show the headset with mic icon). When this happens the phone would start randomly skipping tracks.
I've only had my One for a couple of days, and have only used my bluetooth headphones, so I haven't experienced this myself, but it sounds like this is what's happening.
Solutions:
1) When you plug in your headphones, pay close attention to the status bar icon and make sure its' the correct one. If it's not, unplug them and plug them back in.
2) Use a bluetooth headset
3) Use headphones with a mic and button. Before the problem was limited to when you'd use headphones without a mic.
EDIT: Like I said, I haven't experienced this on my HTC One, but I'm familiar with it from my HTC Evo 3D. If this is verified to be the issue, I'd recommend that a moderator add it to the "HTC One (M8) common problems and questions" sticky.