Even though this says it should be resolved on its own, I don't believe it because we've gotten this message multiple time.
Does anyone have any idea what the problem could be? My team can't figure it out...
You are hitting your Salesforce API limits so new connections by Marketo are being rejected once this happens. These limits are reset every 24 hours by Salesforce, so while it does resolve itself, it's possible to get a new error each day when you reach the limits again.
You need to talk to your Salesforce Admin about upping your available API calls, or perhaps changing how often Marketo syncs, checking which other applications are chewing up your Salesforce API calls, or put in a strategy to minimise the number of calls used per sync round.