I worked with Sitecore Support on this. While we didn't uncover the exact cause of the error, it has been resolved. The only thing that I did from the time that it wasn't working to when it was working was to log out and log back into the Sitecore App Center. At the time I tried this, I wasn't trying to solve the problem but instead get the correct credentials back into Sitecore.
According to Sitecore, this may have been the issue. The first step of sending emails from the ECM is for ECM to contact the SAC to ensure that we have purchased the "Email Delivery" service. It apparently wasn't able to communicate with the SAC and instead threw the error we were seeing. After the credentials were entered again to log into the SAC, communication began working again and no more error.
We'll keep monitoring it, but hopefully this helps someone else down the road.