Found the fix - If this just started happening today, there is also a known Outlook + Gmail Workspace issue where modern authentication fails until you clear the stored credentials in Windows.
Clear Cached Credentials: Open Windows Control Panel, go to Credential Manager, select Windows Credentials, and delete all saved entries related to MicrosoftOffice16_Data:org.outlook.office.google.
After I cleared out the credentials mentioned about I was able to add the account back to Outlook.