Businesses do periodically change banks or account numbers if their account has been compromised by fraud. (This recently happened to my family's business bank account... fraudulent checks were produced - so we created a new checking account.)
You can re-automate all your payments within a day or two on your new account with your NEW BANK. The silver lining is you can assess all these monthly charges - and possibly cut some unneeded services - or upgrade some which you would benefit from.
MOST IMPORTANTLY - Find a bank that is headquartered locally - so you can go see the people who work at the bank occasionally - build relationships - and avoid this type of abuse. If the local bank is sold to a bigger bank - jump ship again.
This sounds like a toxic business relationship and your only TEMPORARY loss is the cash they are holding in your account. You should have access to emergency funds in another bank account - and if you don't - learn that lesson now.
You are ultimately responsible for everything and service providers are just that - service providers. Learn to fire and hire them as often as needed.