We have been rolling this out in our SDK's. It should be available in a few now, e.g., Java.
If you want to code directly against the REST endpoint for updating status, it is a little tricky to get right. I highly recommend you use the SDK's (you might have to wait a few days for your language to be supported). If you really want to use REST directly, as of now, you need to make sure that the status=<new status string> is included in the base string when computing the signature, but that it is taken out of the URL that you PUT/POST to. You would then send "status=<new status string>" in the body of the request.
So here's an example HTTP request taken from the Java SDK's in-code comments. If you use POST, you may need to use "X-HTTP-Method-Override: PUT" in the request header.
POST /v1/users/28568917/status?oauth_consumer_key=77f44916a5144c97ad1ddc9ec53338cc&oauth_nonce=8783759987300271273&oauth_signature_method=HMAC-SHA1&oauth_timestamp=1237853013&oauth_token=8QLGnqFugwmCbIz6pcFbNEMPkG%252FCsZrg4fdqIzXpj88FsZaysd7wJ4eBonbvpAG7MOCFhzDjcM1yp6wvO%252BRaeyruy95QdfpFIHQaHvHL7ak%253D&oauth_version=1.0&oauth_signature=TvlXbt%2FNS0U7SrtUvUfu%2BfJ3kyo%3D HTTP/1.1
X-HTTP-Method-Override: PUT
User-Agent: Java/1.6.0_12
Host: api.myspace.com
Accept: text/html, image/gif, image/jpeg, *; q=.2, */*; q=.2
Proxy-Connection: keep-alive
Content-type: application/x-www-form-urlencoded
Content-Length: 264
status=Hello%20World%20%20%E7%BB%88%E4%BA%8E%E6%88%90%E5%8A%9F%E4%BA%86%EF%BC%81%21%21%20Can%20you%20believe%20that%20I%27m%20now%20posting%20status%20updates%20successfully%21%3F%20~%21%40%23%24%25%5E%26%2A%28%29_%2B%7B%7D%3A%22%3C%3E%3F%60-%3D%5B%5D%3B%27%2C.%2F