Thanks Viktor. I know you're elsewhere on the language spectrum and had hoped someone would jump in here.
From what little I've been able to experiment since asking, it seems that you're right -- there is something in the mechanism of the PUT that's making Valence think my tokens are invalid.
*update* Actually, it's working now. The problem was indeed the PUT, but we were using a REST library for actually sending off the cURL request, and that library was POSTing the PUT. Made that change and it's returning a 200. Yippee!