Try the New-MailUser cmdlet instead...
New-MailUser -Name Ted -FirstName Ted -LastName Bremer -ExternalEmailAddress ted@tailspintoys.com -UserPrincipalName ted@contoso.com -OrganizationalUnit contoso.com
Fingers crossed, this will give the oputcome you desire. If my memory serves correctly, the Enable-Mail User attempts to create a mailbox for an existing AD user (which in this case doesn't exist). In the second attempt, there is an object to work with, so things go ok.
Hope this helps