I would go down this list:

1. Do the new ISPs restrict certain ports/services/ip addresses? (not likely for business access but you never know)

2. Is there a managed/regularly updated firewall on the customer's side? Managed firewalls get regular updates which may change their configurations. This usually happens automatically.

3. Did the hardware or software change in the phone system?

4. Is the customers' own access working OK otherwise? There could be some crapware/attack by a hacker?