It does seem like you should have been getting more useful data back from the service -- I'm not sure I can make too many better guesses from that response than you can. Probably worth checking:
Are you generating a new request token and having the user reauthenticate, or trying to refresh an existing access token? If the latter is failing, you might try the former again to see if it might have just been your refresh code having issues.
Does your original API key behave any differently today? There are rate limits on the YQL APIs, but I think they're way less than you'd be hitting just during development.
EDIT: Heh, adding this reply again because I posted under the wrong ID.