Sorry for the delay in response over the holidays.
I’m not a 100% sure that your issue is with the “*” character encoding.
I do know that I’m able to successfully perform this request by ensuring the character is encoded in the URL and appropriately escaping in the signature basestring:
URL:
https://api.twitter.com/1.1/users/search.json?count=20&q=Bob%20*%20Smith
Signature basestring:
GET&https%3A%2F%2Fapi.twitter.com%2F1.1%2Fusers%2Fsearch.json&count%3D20%26oauth_consumer_key%3DmbmuCGVFTGHZOo5zr5Sx5A%26oauth_nonce%3DaAKXW%26oauth_signature_method%3DHMAC-SHA1%26oauth_timestamp%3D1357141536%26oauth_token%3D819797-L587qRErTHNXXr8kb0eSqj6uCO2xephn1c14RCfies%26oauth_version%3D1.0%26q%3DBob%2520%252A%2520Smith
Authorization header:
OAuth oauth_version=“1.0”, oauth_nonce=“aAKXW”, oauth_timestamp=“1357141536”, oauth_signature_method=“HMAC-SHA1”, oauth_consumer_key=“mbmuCGVFTGHZOo5zr5Sx5A”, oauth_token=“819797-L587qRErTHNXXr8kb0eSqj6uCO2xephn1c14RCfies”, oauth_signature=“5Y4TwqOQPJQTLtVRhfHWQNhLhdk%3D”