The problem was my OAuth base signature string being invalid:
Check that the , used in the geocode value are double escaped - it has to be like 37.781157%252C-122.398720%252C1mi and not 37.781157%2C-122.398720%2C1mi.
Below is a valid OAuth signature example:
GET&https%3A%2F%2Fapi.twitter.com%2F1.1%2Fsearch%2Ftweets.json
&geocode%3D37.781157%252C-122.398720%252C1mi
%26oauth_consumer_key%3D...
%26oauth_nonce%3DToul8
%26oauth_signature_method%3DHMAC-SHA1
%26oauth_timestamp%3D1364420628
%26oauth_token%3D...
%26oauth_version%3D1.0
%26q%3D