Even though my scores are pretty good, I am still in a $25.000 hole. I have a few months ago adopted the following strategy: From my paycheck, I deduct all my expenses for that month. I keep $25/week for play money. Every penny that is left after that goes to my credit cards, paying the highest interest one off first. I am going to suffer like this for about a year and a half, and then I'm done.
My point: payoff your debt. It is the way to go. You will suffer, but remember, the harder you suffer, the shorter it will take. See it as a challenge.
In the mean time you need to get rid of all the negative refferences that you have. Plead, beg, do whatever you have to. And then as has been said before, try to retain a long history, by reopening your cards.
Good luck!