Try a credit union. You can always speak to someone in person about your situation before applying to see where you stand. Additionally, you may want to take your a copy of your reports down to one and see what they think about your chances.
Of course, if you aren't in desperate need of a car, you can always work on paying down your balances and then applying. You will probably get approved at a better interest rate that way.
Im sorry to hear that for you! But we all know that my fico is not based on payment history alone I believe its only 35% of your score! Utilization- you will get a bigger score increase in as little as possibly a month by paying your CC debts down! also you will get the best apr loan and not spend more money in intrest rate fees!!!!Good Luck