First off, please accept our apologies for not replying to this sooner.
It is possible to change the status/mood via the REST APIs. Unfortunately, OAuth does not directly specify how the request itself should be made and how the parameters should be delivered to the provider which leads to some difficulty as you seem to be running into - this gets a bit tricky in the case of PUT/POST since you're dealing with user defined (i.e. non oauth) parameters in the request payload.
Here's how to get this working:
1. Sign your request using the normal oauth signing mechanism (this will result in a request URL that contains both the ouath specific and user defined params in the query string)
2. Remove the non-oauth (i.e. user defined) params from the query string
3. Move the user defined params (i.e. the status data) into the HTTP request's POST/PUT body
4. Make the request
It's best if you used the MySpace SDKs to do the above since it handles all the gory details for you.
Please see the function __call_myspace_api() in the Python SDK (http://code.google.com/p/myspaceid-python-sdk/source/browse/trunk/myspaceid-python-sdk/src/myspace/myspaceapi.py)to see how it handles the PUT/POST cases.