Hi, I am in the same boat as you...my credit is horrible. I have been calling Customer Service and trying to get them to remove old lates...on some companies it works on others it doesnt. One thing i learned is that first get whatever accounts that are late make them current and then try and fight for the lates to come off...it is easier to get lates off when you have made a couple of payments or your balance is decreased or you make a big payment and say that you are trying to fix your credit and give them some type of story why all this happened and that you are really responsible and if they can help by removing the lates to help you rebuild credit...this normally works with CSR who are in the US - not too much with the foreign ones.
Also pull your credit reports so you know exactly what to fight. GW and PFD seems to work for alot of people. That is what I am going to be trying next. And remember make payments on time even if it is a minimum payment...first work on getting some positive payment history and then worry about bring your debt down...outstanding debt is one thing and it is always good to have your utilization low but it is kind of irrelevant when you have 90 day lates.
Good luck