Usually when adding a new 365 user to lync it is as simple as assigning the license and before long they automatically deploy. In some situations when you are running an on premises install of lync and have setup dirsync users never provision. This is true even when you have disabled them in the lync console.
It appears that the cloud based lync will not provision users if they are still setup on premises or have some lync related attributes set. This makes sense as if you have setup users in the portal and licensed them you might not want them to all end up in lync 365 right away.
To get these users objects provisioning simply disable Lync for user on the in premises lync server control panel then clear/not set these attributes:
> msRTCSIP-DeploymentLocator
> msRTCSIP-FederationEnabled
> msRTCSIP-InternetAccessEnabled
> msRTCSIP-Line
> msRTCSIP-OptionFlags
> msRTCSIP-PrimaryHomeServer
> msRTCSIP-PrimaryUserAddress
> msRTCSIP-UserEnabled
> msRTCSIP-UserPolicies
Double check the user is licensed for Lync option 2. Soon they should appear on the lync portal and be able to sign in. (Assuming you have setup your DNS/Auto discover.