Tried with both API 1 and 1.1.
API 1 produces a different error message: http://pastebin.com/jTJZH3tt
It worked yesterday, I was able to post the same tweet. The only thing that was different yesterday: I initially sent the update without the cookies that I received from request_token (by mistake), and got a 401 (forgot exact response). I then reissued the request using Fiddler by manually adding in the cookies from request_token.
This morning I corrected the problem in my software which prevented sending the cookies, but no matter what I try, it still fails with subject error.