Have you tried the bonus gift thing? A tool kit and movie tickets worked well for us.
A different twist on the bonus gift is to tie in with a community cause. A local child abuse center was having a Three Dog Night benefit concert and we gave free tickets when a new account was opened. We actually ran out b/c the concert was a sell out.
You can also do $10 to the local United Way each time a new checking account is opened or $10 to the school of the customer's choice and the school with the most gets an extra $500.
You can ask your business customers to let you come in and meet with their employees and open accounts on site. (Don't take deposits, just do paperwork.) Most businesses have a staff meeting and they would love for you to bring food. You can combine it with an educational message such as saving for retirement, the benefits of direct deposit, or protecting yourself against identity theft. Throw in a free dinner if they fill out the new account paperwork that day.
The most successful month we've ever had was when we did an internal sales contest "Battle of the Sexes". It was men vs women on referring/soliciting new accounts. The winners had lunch served to them by the losers, their shoes shined, and their cars washed. Guess who won...the women of course!
