I'm sorry that happened to you. There's some things that you need to know about your score.
1. What makes up your score:
35?ayment History
30?ebt to Available credit Ratio
15?ength of time establishing credit history
10?ypes of credit established
10?nquiries and New accounts
2. What's hurting your score:
Providian & Captial One
3. What you can do to improve your score.
Ok, having said all that let's look at the bad stuff first. Let me start off by saying that there's what's called a statute of limitations for debt. One for collecting debt which varies by state. And the other is the federal 7½ year statute of reporting debt called the Fair Credit Reporting Act(FCRA), which starts from the date the debt first went delinquent. The statue of limitations(SOL) for collecting debt is pretty much the time in which collectors can take you to court to make you pay what you owe. (Click this link to find out what the SOL for your state
http://www.creditinfocenter.com/rebuild/statuteLimitations.shtml) What this means for you is that if the SOL is expired you're legally not responsible for the debt anymore, however you still would have to present this as a defense if you were taken to court, and also you could use this as a powerful bargaining tool to deal with collectors.
It's a good chance that the SOL for reporting the debt may soon be expiring, so it could be used to your advantage to possibly wait it out. If you do decide to try to negotiate with the collectors, your goal is to neogtiate what's called a "deletion payment" which is making a payment in return for having it removed from your report. I posted another link that explains a little more about how to settle old debts(
http://www.creditinfocenter.com/debt/settle_debts.shtml) but also keep in mind, you may not have to especially if the Federal statute may soon be expiring.
Let's say that you're fortunate and successful in getting those items removed, it could possibly hurt your score at first because you don't have any open lines of credit to compensate for the bad that you do have. The easiest way to do this would be by opening up a secured credit card. You would have to put a deposit upfront to get the same in a line of credit, but think of this as building credit with a savings account. This works especially well if you already have money saved up in a savings account that you're not touching for a while. Like for example, you mentioned in another question that you had money saved up for a down payment on a house. That could be used for the deposit, and you could get a credit line in the same amount. Make small purchases that can be easily paid off on time every month and usually after a year, you not only get the deposit/down payment money back with a little interest added, but also you've ilt credit to where the secured card will either convert to a regular one or a better card will be offered altogether. If you're going to save up for a down payment, you might as well make that down payment work for you. Oh, and I also forgot, while you're building credit add to the deposit/down payment money to increase your credit line. The higher the credit line, the better it will look on your report. Also you may want to try Orchard Bank as a 2nd major revolving account. They offer cards for people starting out and starting over, when it comes to credit. Then to round out your open revolving accounts, I'd try for a department store card, one that you'll use, but not overuse, for example home depot, lowe's, sears, etc. Since you've paid off a car already, that will help the installment credit portion of rebuilding your score.
Also, if you've been paying rent, utlities, phone, cellphone, and insurance you should enroll with PRBC to have it reported as alternative credit. The bills I just mentioned do not show on your regular credit reports, yet every month you pay, and some of those payments are more important than credit card bills! PRBC is a new credit bureau that feels these payments should be just as important. They score these reported payments in a report which can be used along with your regular credit reports as a supplement. These reports can even be useful in getting a mortgage (hint hint). I posted links to their website, which I strongly suggest you check out. I'm confident that they will help you. I also posted those links to help you deal with the current debt that you have.
I hope that this helps,
Good Luck!