HTTP header UTF-8 Characters

I am trying to populate a header with a UTF-8 character. Lets assume: 私はガラスを食べられます。それは私を傷つけません
When I do it - I get little boxes.

So I tried URL encoding it.

However, when I get a response from the service, I do no get a good response with the encoded name. I get jibberish. I basically send it ONE kind of encoded string. I get something completely different.

I have encoded and decoded using this link: http://meyerweb.com/eric/tools/dencoder/

The PROBLEM really is that the REST Client plugin for Firefox will do it right.
SoapUI seems to have problems with it. What are my options here.
This limitation makes moving to soapUI pro unfeasible.

Help?!?!