Unfortunately, asking is not a guarantee of approval, even while demonstrating your ability to pay. Normally, I'd say hangup and call again, but given the situation that you've outlined, I think you may need to PIF the outstanding balance on the closed card and get rid of that collection before you can butter BoA up enough to loosen their purse strings.
It's a recurring theme all over these boards right now. Taking too long to pay off a balance on an open account is credit line suicide these days. Letting a balance linger on a closed account with a history of delinquent payments is not good. Add a collection to that, in the *current* credit climate, and you might want to knock-on-wood that BoA hasn't zapped your card in good standing.
A credit score isn't everything. Credit history (particularly internal history) can be just as compelling (if not more) to a creditor who you're asking to extend *more* credit, during a time when they're trying to reduce their exposure and liabilities. Letting a balance on a closed account linger for years might be a flashing neon sign that you'd be in serious trouble if you got more credit and maxed it out. You'll need to demonstrate that you're not in over your head already, and that your ability to pay is not going South (work the on the collection). Then, use your current card liberally while PIFing every month for a few months. I think they'll have a change of heart. 
Otherwise, I just want to say that I understand your frustration. I was stuck at $2k (the amount of my secured limit that remained after it unsecured) for years until I cleaned up my act, and quit giving them a reason to turn me down. Over the last 6 months, I've gone from 2k to 7k, just like that. But, I had to show them that I didn't need the training wheels any more. Sadly, they wouldn't just take my word for it! LOL! 
@natasjlp wrote:arrrggg... just got off the phone with BofA backdoor number about a CLI - I have a CC with them for $1300 for 5 years perfect payment history. Increase denied! what the heck?!
They said it was because I had another closed account with them that I am still paying off with them. The card in question has had many many delinquencies that is for sure - had serious trouble with their phone payments - still POed about it - they kept dropping my payments then I would have to reinstate them - months later they didn't take a payment - fell behind again [don't want to get into it - blood boils]. So it is riddled with missed payments. However, it has been perfect since September 2007 - soo... what the heck...
Is there another backdoor number I should use? maybe I used the wrong one? Sounds like the pulled an Experian report because they said I had a Verizon collection which I need to dispute, that does not show on my EQ or TU - only EX...
I don't know - just needed to vent... arrggg... My EQ is 701 TU 690 who knows what my EX is - prob not as good. With a FICO in the 700s how in the world could I be denied for a CLI with a current limit at only $1300!?