What method are you using when trying to verify your domain with Google? To verify your domain, the password protected page must also be disabled so that Google can verify your store. Is this currently disabled or enabled on your store? To remove the password on your store, you can follow the instructions in our help doc: Preparing Your Store - Remove Your Online Password Page.
I recommend using the meta tag option listed in our help doc here to verify your domain.
Let me know if that helps!