Microsoft seem to have resolved an issue with the synchronisation of users profiles between the different services within Office 365. Previously once a user had been added through the Office 365 portal, their information would not be synchronised with the other services, such as SharePoint online. This meant that should the user start a workflow, it would fail due to the user profile not being found in SharePoint online. A few weeks ago we added two new users to the Office 365 portal, and these both did not synchronise to the other services. However, as of yesterday these user profiles now appear in SharePoint online. Hopefully this issue is now all resolved.