We updated the certificate last week and haven’t had any issues yet. Did you install the certificate on all your appservers including task agents? Are you getting the error when you try to test the connection in Company configuration and did this just happen after the May 10th update?
Are you still using the current Avalara URL https://avatax.avalara.net? You can try reinstalling the certificate and verifying it was added to the keystore. When did you do the initial install in Production?