You're going to have to get a copy of your CHEXSYSTEMS report to first, verify that the negative was reported by your ex-bank to CHEXSYSTEMS. If it's listed (and you'd know already because chances are you'd be denied a new checking or savings account), chances are excellent that if you contacted your old bank (since so much time has passed since the issue first arose) they would probably have the negative deleted from your CHEXSYSTEMS report.
Then you're going to have to get all three copies of your credit files if you haven't done so already (Experian, TransUnion, Equifax). You might find that not all of your derogatory accounts are listed on all three - so you could, in theory, be working with one or more credit files that are actually clean.
Since then I applied for a couple checking accounts with Wells Fargo and Capital One and was not denied nor was there any indication of my old bank's balance so I don't believe they reported it to CHEXSYSTEMS.
I do have all 3 copies of my credit files and indeed all 3 bureaus have all the account mentioned above so it is something I do (and am in the process of) need to clean up.
Second, if you're debts are paid, use every legal means necessary to get thos negatives wiped off - you can try goodwill letters, you can try straight up filing diputes with the credit bureaus and making your old debt holders verify the information (and if they can't meet the requirements of the law, the items will get deleted). Most here will tell you to go the goodwill letter route; I advise using every legal means at your disposal, however.
If the good will letters don't work; given the fact that I've paid off all the outstanding debt, what could I state in my dispute?
As of February 2013 I had NO CREDIT and I had 3 negatives on my credit files. By April 2013 (2 months later), I had opened and maintained what you see in my signature AND I wiped out all my negatives from my credit reports. I was aggressive in handingly my credit issues and as of almost June 2013 everything seems to have worked out well...
...so it's very possible to move very quickly on fixing your credit if you just do it and not get confused and bogged down by all the different opinions and advice. The important thing? Do something. Anything!
Congratulations! I agree completely, the important thing is to do something and I have at least started the ball rolling. Hopefully I will acheive similar results 
I would consider a capital one card before going for FP or CreditOne. I know I got approved for their rewards card with low limit when my scores were low 600's. They are sub prime but have fewer fees.
