Cannot connect to Office 365 with PowerShell

I want to connect to Office 365 through powershell, referring to the tutorials a very simple task. But apparently not for me.

I think I missed a simple but important trivia.

Some info:

• license is Office 365 Buisness Essential
• Azure AD is running
• I'm able to use powershell remoting (WinRM) with other servers
• I use the admin account
• I use my domain and tried the onmicrosoft.com domain
• two-factor authentication (additional security verification) is configured

I tried the following

PS C:\>Import-Module MSOnline
PS C:\>$msolcred = get-credential
PS C:\>connect-msolservice -credential $msolcred
connect-msolservice : The user name or password is incorrect. Verify your user name, and then type your password again.

and

PS C:\> $O365Session = New-PSSession -ConfigurationName Microsoft.Exchange 
    -ConnectionUri https://ps.outlook.com/powershell 
    -Credential $msolcred -Authentication Basic 
    -AllowRedirection
New-PSSession : [ps.outlook.com] Connecting to remote server ps.outlook.com failed with the following error message : Access is denied. For more information, see the about_Remote_Troubleshooting Help topic.

and I used a different connection uri

PS C:\> $Session = New-PSSession -ConfigurationName Microsoft.Exchange 
    -ConnectionUri https://outlook.office365.com/powershell-liveid/ 
    -Credential $msolcred2 -Authentication Basic 
    -AllowRedirection
New-PSSession : [outlook.office365.com] Connecting to remote server outlook.office365.com failed with the following error message :
[ClientAccessServer=VI1PR05CA0019,BackEndServer=,RequestId=5d73dec9-b3ee-4e71-9ddd-bdaac8f79998,TimeStamp=3/7/2015 8:17:50 AM] [FailureCategory=LiveID-InvalidCreds] Access Denied For more information, see the

Help is really appreciated!

It doesn't look like two-factor authentication is supported by PowerShell for O365.

http://community.office365.com/en-us/f/148/t/222763.aspx

"If an administrator account was enabled Multi-factor Authentication, PowerShell will not work when he connects to PowerShell with this administrator account. Ensure you create a service account with a strong password to run PowerShell scripts and do not enable that account for multi-factor authentication."