Ring the bank and lock your account.
Tell them you have had your details stolen and that you will come into bank to personally authorise payments from a said date, including all direct debits etc.
It will be loads of hassle with DD and salary etc but you can lock your account if you think your details have been compromised.
If the bank get funny arse tell them to cancel every single direct debit from now and every single payment made from the day you where compromised.
Make sure you have a passport handy and details then pop into another bank and open a new account the same day.
Tell bank A to screw themselves.
Start a fresh with bank B.
Phone every single person who has direct debit and explain, they will be very understanding.
The is always a way, screw the banks, Ebay and Paypal! I hate them with a passion!