Salesforce Integration - An exception occurred while saving the integration

I've seen this error a bunch of times and the only solution that has worked 100% of the time is to delete the package and reinstall. But you should follow these steps below before deleting and reinstalling the managed package (it helps to use an incognito window of Chrome as you may have other instances of CRM or MC open):

1. You mentioned that you checked the permissions. Double check that the authentication settings are correct in CRM. And double check that you have applied admin permissions.
2. Check the Permission Sets are assigned correctly to the correct user
3. Also in CRM, you should be able to click the Connect to Marketing Cloud blue button.
4. Theoretically, the Setup Wizard should create the connection and add the whitelist IP addresses automatically.
5. If you're unable to get into the configuration settings, use this URL hack and add "apex/marketingcloudconfiguration" at the end of your URL. i.e. https://etxxxx.xxxx.visual.force.com/apex/marketingcloudconfiguration.
6. Refer to the image above: Under Manage Business Units, make sure you have the business unit checked
7. Under Manage Users, make sure you have your MC user checked for both User and Admin.
8. In Marketing Cloud > Setup > Users, click the "Integrate" link and add your CRM login and save it so it shows Integrated.

8. Back in CRM, in the Marketing Cloud Connector Settings, check that the API User Username matches your MC User. If not, then click the Change API User link.

9. If all else fails, delete the managed package and re-install the managed package.

I would make sure you try all the steps above before deleted and re-installing (I have a feeling it could be #2 above). But since you are on multi-org, I assume that this managed package is a fresh install in the org and it should not be an issue to delete the package and reinstall it.

I ended up creating a support ticket. Support said that all the settings on our side were correct and that the fault was on their side. They told me that they had to "reset the servers", which sounds very vague, but in the end it worked and I was able to connect all accounts successfully.