I was in a similar position last year. I was unable to open an account, due to checksystems/telechecks (not sure which one) I had a BOA account that was overdraft too long, due to an autodraft that took out way more money than they were supposed to. Either way, i was unable to pay the money, it was $500, and i'd just moved, so of course i was broke. i tried to pay down the negative to a positive balance, but after so many days of a negative balance, BOA automatically closes your account. Anyways, I spoke with a customer service representative, and explained my situation. She told me the date that I had to pay the balance, before the account was closed. As soon as I got my taxes, i went to my local branch to pay the balance, but they'd closed it the day before. (just my luck), anyways, i stll paid everything in full. tried to reopen the account, that day, but was told my fico was too low, and the system wouldn't allow her to. (i'd been a customer for over 10 years). anyways, she told me to try back later in a few months. a year later, i noticed that there was a collection account from boa for the balance i'd already paid. apparently they still sent the account to collections, even though i paid it, because it takes a few weeks for the money to clear their systems, or so the manager said. i called their collections dept, and was told that they still had that i owed them $65, the fee for them to contact collections. but i explained that it never should've gone to collections in the first place. she immediately deleted it, and all of the entries in my credit report, and mailed me a letter explaining the situation. my point in the story is that although you may have paid the account, it may be some type of internal error, that they haven't contacted checksystems to show that it was paid, because i was later able to open an account at another bank. i think boa won't allow me to reopen an account ever. which saddens me, because i really think they are the best bank. i guess im on a blacklist forever.
but, depending on your state, there are banks that don't go through checksystems, and some that do, but as long as all checks have been paid, will still allow you to open an account. in maryland, provident allows you to open an account, BOA does as well as long as all checks are paid in full, chevychase bank, and m&t bank as well. hope my experience helps