Re: Invalid client id
Can you confirm you are trying to log into Production vs Sandbox?
The reason I ask, is the first url you posted is production (https://rest.zuora.com/oauth/token) and the other is sandbox.
For sanbox, oauth, use https://rest.apisandbox.zuora.com/oauth/token
If thats not the issue, please post the full api call (minus credentials) and we can troubleshoot from there.