Not every issue that looks similar on the service has relations to each other. Some of our API methods in API v1 are stricter than other methods with OAuth and HTTP. API v1.1 as a whole is much stricter about both OAuth and HTTP than API v1. Very subtle errors or inconsistencies in HTTP libraries and OAuth libraries can cause issues.
Can you detail your request to users/lookup that is failing? The exact URL you’re executing. The exact parameters you’re sending and whether they’re in the query string or in the POST body. The HTTP method you’re using. Your signature base string. The HTTP headers you are sending. All of these are participants in what can go wrong in HTTP and OAuth.