I followed the process here:
At the end there is an Important note about an exchange online user getting this error (which I am getting):
Cannot expand the folder. The set of folders cannot be opened.
Network problems are preventing connection to Microsoft Exchange.
I moved a mailbox from On-Premise to the cloud, which left a 'Remote User Mailbox' object behind, so the user has an exchange object On-Premise. I tried deleting that object and created a MailUser object instead, but I still had the same issue (I since changed it back).
Any troubleshooting suggestions?