When you click Track in CRM on an email within Microsoft Dynamics CRM 2013 for Microsoft Office Outlook, the email is not tracked in Microsoft Dynamics CRM. This occurs on a new Microsoft Dynamics CRM Online organization with the Fall '13 Service Update
By default the Process Email Using option within System Settings is set to Server-Side Synchronization. Also the default Incoming Email and Outgoing Email settings for all mailboxes are set to Server-Side Synchronization or Email Router.
When a mailbox is set to use Server-Side Synchronization or Email Router and the Process Email Using setting is set to Server-Side Synchronization, Microsoft Dynamics CRM 2013 for Microsoft Office Outlook relies on the Server-Side Synchronization process to track the item in Microsoft Dynamics CRM. The Server-Side Synchronization feature is not currently supported with Microsoft Dynamics CRM Online. This causes the Track in CRM action on your Outlook emails to fail with this combination of settings.
Microsoft had release a KB article which has the resolution step in detail.