So you've already checked that you have the necessary rights.
Did you install Powershell 3.0 CTP?
Powershell 3.0 CTP seems to have some issues with the SharePoint snapin, and will not give you the above error. Uninstall it, and things start working again.