My story: I was given the option to change my boss for the first time in 2006 or so. At this company, I'd already been promoted several times, ostensibly on merit, which involved a different boss each time. This event was different. The team was growing and we simply needed more people doing similar things. I decided my relationship with a (somewhat older) peer-turned-manager would be better off if I didn't report to him.
Had he been a bad boss? Not really, but he wasn't a good boss. The new boss wasn't any better or worse. Old boss and I both spent the next year slightly miserable, but I wouldn't have known how miserable he was until he suddenly left the company. And then he hired me away a few months later.
He also fired me a couple years later. Why? I was sick of the job, and I mostly deserved it; we were also at a smaller company now, where more egos were crammed into one room. I'd also literally been given a second job and a second title, complete with a second boss, who was also my boss's boss. (No pay increase, of course.)
Was it more work than I could handle? Not exactly. Was there a mismatch between my responsibility and my power? Absolutely. Did losing this job damage my career? Not in the long run, and I learned far more valuable lessons about the need to simply work differently with different people.
I think stories like this are close to the best possible outcome when you have a bad boss. And I think the moral here, is that a Voltron Manager is something everyone should have regardless of how good their current manager may be.