Its hard to get a bank account with bad credit.
You can look on improving/enhancing your image.This should involve clearing off debts in any small installments as possible, which will let the bank know you are "trying".
Credit card dues must be cleared off as well, consistently.You could apply for pay day loans then.
RBS are the only bank I know that will open a Business account for people with less than perfect credit ratings. You will only get a debit card and no cheque book, but its a start