Phone up telephone banking and ask why the loan was turned down - AIB, unlike a lot of institutions, are very upfront about telling you why the loan was rejected. Then tell them that you want are going to close all your accounts unless this loan is approved. See what happens.
If they don't, make an appointment for your neaest PTSB or National Irish Bank and switch all your accounts, including your credit card. Make sure you make it very clear why you are changing. NIB I know were very generous to me when I originally switched from AIB to them in 2004, and I'm now on my 2nd car loan having cleared the first in full with no missed payments. In fairness at the time I changed not only was my credit history crap, thanks to BOI not updating loans it was also inaccurate and before I got it corrected it looked like I hadn't paid off a loan which I had. Despite this I was still able to get a 3k loan from NIB (not to mention a VISA card and current account).
I've tended to move away from paying monthly direct debits as I find that external circumstances like not being paid on time or the fact that most utility companies put DDs out on different dates every month (eircom, ESB and Bord Gas take note) which makes it impossible to predict when they are due makes it impossible to budget.