The issue is that those are UTF-8 encoded so you'll need to decode those first. I hit this a while back and wrote a script to get around it.

Code:
function urldecode_utf8($input)
{
  $input =  urldecode($input);
  $result = preg_replace('/%u([0-9a-f]{3,4})/i', '&#x\\1;', $input);
  return html_entity_decode($result, null, 'UTF-8');
}
That should do what you need.

Edit:

One note: ensure that you set the content type header to output UTF-8 contant or it'll render incorrectly.