Exchange online users - issue with full permissions and editing calendars on Prem

We have a hybrid environment we recently setup and are slowly moving users mailboxes to the cloud Recently, we have uncovered an issue that we are not sure how to get around (other than recreating the accounts). Our Hybrid environment involves a 2010 and 2013 exchange server and the goal is to move everyone to the cloud. We have been not having any big issues with users that had accounts on Exchange 2010 or 2013 and were migrated to the Cloud. The issue we are seeing as that with newly created accounts that are made within our Exchange 2013 environment but set the mailbox to Office 365 are having permission issues. These users cannot gain full permissions to user mailboxes ( send as also does not show the user as available to add) We receive the error "The set of folders cannot be opened, The attempt to log on to Microsoft Exchange has failed". Or a prompt with the username prepopulated pops up waiting for their password, this does not work.  Interestingly enough  I can open the mailbox that was given full permissions to within outlook.com (webmail) for this user. We also seeing issues with not being able to edit/add calendar entries for onprem meeting rooms. Just to reiterate users that originally lived on Prem have no issues(so far as I can see) with these permissions.

In the short term we will obviously be creating the mailboxes on prem, wait a bit and then move them to the cloud, but does anyone have any ideas what is happening here? I was under the assumption this was the process to use until we have everyone moved the cloud.

Any help would be great!