Can't get Brightkite OAuth API to work

Hey, I am trying to use the Brightkite OAuth API and I am having some trouble.

I can't seem to get an initial RequestToken. I tried both a POST and
GET and I always receive an "Invalid OAuth Request". I triple checked my
initial app key and secret, and everything seems to be fine.

Anyone else had this problem? I use OAuth for a number of other
services, and I have no problem with requesting and authorizing.
Thanks.