"SendAsDeniedException" when trying to send emails since moving to Office 365

Have a client who was emailing SO Orders and Invoices with no problem when they hosted their own Exchange Server. Recently moved to a cloud based Office 365 solution and now when they try to send a test email or a Form they get, "SendAsDeniedException" (a little more of the message is below). We can send from another email address but of course that's not the address they want to use, or used to use. I'm thinking there must be a verification setting on the server but it's outside my realm to know what to tweak.
More of the message:
554 5.2.0 STOREDRV.Submission.Exception:SendAsDeniedException.MapiExceptionSendAsDenied; Failed to process message due to a permanent exception with message Cannot submit message.