The Exchange Online server for your Office 365 account uses a different default authentication scheme than Exchange on-premises. In most cases, you won't notice the difference – except when you're using the EWS Managed API to call Exchange Web Services (EWS). Then you'll quickly find out that something has changed, because your client that worked before will start failing with a 401 Unauthorized error when it runs Autodiscover.
Exchange Online uses basic authentication, and chances are your client is expecting to use NTLM authentication. The problem is simple, and the fix is simple too: you need to change your code to create a set of credentials for basic authentication.
Typically, that means changing a line of code that looks like this one:
NetworkCredential credentials = CredentialCache.DefaultCredentials;
To one that looks like this one:
NetworkCredential credentials = new NetworkCredential(UserSMTPEmailAddress, SecurelyStoredPassword);
Of course, the devil is in the details, and in this case it's that parameter called SecurelyStoredPassword. You'll need to make sure that your client gets the user's password and stores it, for example, in a SecureString object instead of a plain text string. For a more recent example, you can take a look at the Credential Locker for Windows 8 store and desktop apps.