I have been in IT and Project Management for a long time, but when I have to give references for background checks (federal and commercial) they want previous managers. I have two instances where I was hired by one manager that I really liked, then was moved to a different project or a manager quit and I got stuck with bullies. If they didn't hire you, they hated you or made your life miserable. How do you give them as a reference or explain why you don't want to without sounding like a "problem" employee?
It depends on the type of background check. Generally the ones for the US Government do not care if your manager recommends you. They care if you worked there during the period you claimed you worked there. They also do not care if you have a mistress that you are providing for so long as you tell them about it. If it is not illegal do not hide it from them.
They are looking for inconsistencies that make you untrustworthy. For this reason I provide them with the name of my manager, and the name and number of the HR Manager. The HR Manager can verify your employment and if you are eligible for rehire. Unless you were terminated because of a safety or fraud risk you are probably fine.
This is not true of all back ground checks just those done for employment with the Government. This also applies for access to protected facilities and general secret clearance but I have heard it gets stricter if you are doing area 51 or NSA type stuff though I have no personal verification of that.
Honestly and openly.
I mean one thing is to avoid complaining on your bosses or companies (after all who wants to hire a whiner) but another is honest opinion about your current situation. It doesn't have to, or need to, be put in harsh words. "I don't get on well with my boss" sounds way better than "my boss is a jerk."
A recruiter may or may not ask you to go into details. If they do I'd try to be as objective as possible, even though I know it's almost impossible in such case.
Trying to come up with a story to cover the issue is likely to make the whole thing even worse.
1 - verify background check vs. reference check. As Chad said - both US Clearance and many work history checks are done by an external party simply to verify truthfulness and work history. If they are paying for 10 years of experience, then they are verifying you have the 10 years you said you did.
2 - if it's a "background check" and not a character check - then you may also be able to provide a work hotline or access to your HR to verify employment history. Some work places even say that bosses can't answer reference checks for various legal reasons. So if they just want work history, give them what they need. Chances are, it's preferred as they care more about speed than finding a busy manager.
3 - if it's a character check - look for alternatives - how many of your recent managers have been good, and how long did they manage you? Can you give peer references? Or cross-manager references? For example, a manager you worked closely with on another team. Very few places want only "direct reporting" managers - in many cases, they are sensitive to the fact that you want to continue working until you get an offer!
As Pawel said - if you must, state simply, honestly and judgement free that your current not-ideal relationship is a reason you are looking. But avoid sticking to the negative - work to find a reference they can use.
Give references from people that will speak well of you. List the positions but do not give references for others.
If pushed about it say "we disagreed on some things and had different view points".
If pushed on that try to focus on how you were into things like (say) testing, better communication to the customer, stuff like that that are professional and sounds good. Pick some that are true because most people can't lie well, but they think they can.
How do you give them as a reference or explain why you don't want to without sounding like a "problem" employee?
You can't because, likely, you are a problem employee. There are certainly bad bosses; in fact, I'd argue most one would encounter would likely lean to that bad boss side. However, the description that they are "bullies", i.e., they are bullying you or you feel bullied, implies something other than they were bad bosses. The perception of being bullied is very interesting and something you should take a serious look at.
They ask for references you gotta give 'em and you're going to get what you are going to get. In the mean time, take a strong, hard look at what you are contributing into the bullying dynamic and start working on changing that. You can't control the boss you are going to have, but you can control you.
Addendum: I knew I was going to get some reaction with my chosen words and possibly some negative votes. But that is exactly this OP's challenge: my drawn assumption--he being a "likely" problem employee--is exactly the assumption many or most or even all hiring managers would draw with the words this OP is using!! Is (s)he a problem employee? Have no earthly idea. But describing being bullied by your bosses--not boss--will not fair well for the OP. And, I'd bet, without knowing him or her, that his or her contribution to that dynamic was quite significant. And his or her contribution is the ONLY piece that she or he can control for the future.
I know it was harsh, but that is what (s)he will likely face secondary to those issues. And one last point: there is something a bit off when a person can identify only external reasons for their problems and hold themselves as victims.