We had the same problem. For us it was caused by the GPO setting "Do not log users on with temporary profiles" : Computer Configuration\Policies\Admin. Templates\System\User Profiles
If this is enabled, try disabling it. When you "run as different user" windows creates a temp profile for that user. If the GPO configuration above is enabled, Windows can't create the temp profile and will display exactly the error you're seeing.