Kate,
The thing to remember -- if you have shot credit -- is to demonstrate a payment history with no lates and with the lowest possible Utl. What your CBR doesn't show is if you used the card or not, when you're paying it down. Just that you have an active balance.
If it takes you a full year to pay off the cards -- with or without fees -- by the time you reach May or June try to have the balances below 45%, then your FICO should be quite a bit higher than what it is now.
Closing cards is not the best strategy, because it reduces your aggregate CLs. Even if you are paying for CLs, keep in mind that until you have a FICO above 650 you might have trouble getting a prime card that has no annual fee. What you should try to do is get a prime Mastercard, maybe a Chase or Citi. And a AMEX, which does carry an annual fee though.
The monthly fees that suck ilk as First Premiere charge is the cost of rebuilding, so don't sweat it. When paying always include the cost of the finance charge and the monthly fee, to watch the balance reduce as fast as possible.