I had been struggling with this problem for quite some time; every now and then Pidgin would refuse to connect to Google Talk and give me a Not Authorized failure message. All credentials, server details and network conditions were unchanged. I installed Trillian and found that when Pidgin failed in this way, Trillian wouldn’t connect either.A few forum threads would suggest updating to newer versions of Pidgin/Trillian or changing servers and re-checking credentials; most were dated threads which are irrelevant today. Pidgin would resume working as suddenly as it stopped, but sometimes after days of being unable to connect. All this time, the GMail based chat would work without issue, a veritable PIA!
I found, entirely by accident that my account had an Account Locked status if I logged in with the official Google Talk client. Unfortunately, I didn’t have their official client installed all this time, so I didn’t realize this earlier. Attempting to login to chat at this time would present you with a captha and after passing through this, you would be able to connect on Pidgin too. Apparently Pidgin and Trillian are foxed when the account is locked and don’t know how to proceed; I have no idea why my account gets locked either… I also don’t know what the platform independent solution is because AFAIK the official client is available only on Windows; logging in and out of chat in GMail didn’t help.
TL;DR If you get a Not Authorized message in Pidgin or Trillian, login using the official Google Talk client, pass the capthca test and you will now be able to connect again, even after quitting the official client.