Читаем доки, они рулез: "urldecode() function is not supporting UNICODE characters coding, like %u0627 for the Arabic letter ALEF (& #x627; in HTML). So when you are passing the Unicode chars through GET/POST, you will get only encoded string"
Полный текст: http://www.php.net/manual/en/function.urldecode.php