Actually, the best thing to do if you have bad credit is challenge everything on your credit report. First you have to obtain copies of it, currently I believe there are three major credit reporting agencies, and they changed a bit recently, so msg me if you know this information to be different:

Experian (TRW)               Equifax                  Trans Union
P.O. Box 2104                P.O. Box 105873          P.O. Box 390
Allen, TX 75013-2104         Atlanta, GA 30348        Springfield, PA 19064
(800)682-7654                (800)685-1111            (800)916-8800 

Then challenge every negative mark on there. Challenge late payments, overdue payments, missed payments. Challenge people inquiring about your credit. Anything on there you simply write the credit agency a letter stating that you do not believe the information to be accurate. They in turn contact the reporting agency and ask them to prove what they have reported in your name. If the creditor does not reply in a certain amount of time verifying that you indeed did miss a payment or what not, then the mark on your credit report is immediately removed never to be seen again.

Chances are half the time paperwork gets lost, records are only kept for a certain number of years, and credit agencies don't have the time and personnel to go looking through back records to see if you actually did skip a payment on your car loan.

When you go to one of those places that promises to clean up your credit history, this is exactly what they do. Write a few letters and hope for the best.

One last thing... keep in mind that the three credit reporting agencies all have individual copies of your credit record. So anyone looking at your report can go to any one of the three companies. So when you write your letters, write three copies, one for each reporting agency!!