Some things you can try: (1) Check If you already installed the module by means of the SharePoint Online Management Shell...if so, uninstall it (2) Try to us the -force parameter in the Import-Module cmdlet
I had the exact same problem, mine was caused by Microsoft.SharePoint.Client.dll installed in the Global Assembly Cache.
To resolve the issue, (1) Navigate to C:\Windows\Microsoft.NET\assembly\GAC_MSIL (2) Remove the Microsoft.SharePoint.* assemblies (3) Uninstall the module with Uninstall-Module -Name Microsoft.Online.SharePoint.PowerShell
After reinstalling the module from the PowerShell gallery, the module worked flawlessly.