I had a BoA account a while ago, but after a similar incident decided to take my money elsewhere. And really that's all you can do. Let them know why you're leaving, tell them where you're going to take your money (Chase for me), and get the heck out. Even if they fix the problem immediately, like you said, its the principles behind what went wrong. Any company that practices business like that, you don't want to be a part of, ESPECIALLY with your money.
Also, one trick i have done with deposits, esp if you have the check in hand. I would cash the check at BoA, then get back in line and go to a different teller (or branch), then deposit the money. Bc cash shows up as immediately available, i had no worries about a slow deposit time.
I'm not sure if they have somehow corrected this loophole, but sometimes when I needed money there to be in my account THAT DAY. I would do that, and it always worked.