Difficulty just setting up the Social Connections (unauthorized)

I tried adding Google and Facebook connections, and when I “try” them, I get:

{"error":"unauthorized","error_description":"invalid credentials"}

I could not reproduce the situation when I tried the Google social connection both with Auth0 developer keys and my own keys. If the situation persists you should provide additional information about the exact steps to reproduce and also context information like the region in which you have the service domain (US, EU, AU).

This looked promising: http://community.auth0.com/answers/742/view (for them it was a rules issue). So, I checked and I was testing the rules out. So, I removed any rules I had… and the problem is still there.
Then, I created a new tenant to try this out from scratch, and it worked! Darn, so why is my tenant not working but a new tenant is working? It can’t be rules because I removed those (unless they are still lingering somehow).

Ok, it looks like I had a Default Audience in my settings, from the first time that I used Auth0 on another project. So, I just made sure that I don’t need Default Audience and then removed it.

It looks like things like “rules” (see http://community.auth0.com/answers/742/view) and some of the tenant “settings” could affect the ability to use the social connections.