When Drupal is running under certain FastCGI web servers, e.g. those used at Acquia, Authentication headers are stripped from HTTP requests before they hit Drupal. Thus, attempts to authenticate Consumers with valid secrets and keys result in 401 errors.
N.B.: this is not a bug with the OAuth module, per se, but the use of this module with FastCGI does result in the pretty-baffling situation described above.