I think it might be a problem with the signature checking code. I'm seeing this in the www-authenticate header
This was a combination of 2 problems.
One, Nagesh mentioned that my * had to be coded as a %2A. This was correct, it should be a %2A. The YQL console actually DOESN'T encode it, so be careful when just copying and pasting.
The second was I did a bunch of jiggering with encodings and other things in my library and all of a sudden it worked.
So, I give you a working oauth library in python :http://github.com/ptarjan/python-oauth/ . It is a very mild change from the one on oauth.net/code with a bunch of helper functions that should make oauth slightly easier than the 'brain surgery on a roller coaster', that it is today.