Fresh install of WordPress. No wordpress plugin enabled.

Permalink structure:

/%category%/%postname%

After I click any single publish with this particular permalink structure, it shows me a mistake:

This really is somewhat embarrassing, is it not? It appears we can’t determine what you’re searching for. Possibly searching, or among the links below, can help.

The problem is the fact that it is so unpredictable.

Category URL is alright even when category title consists of Chinese:

http://ubeni.org/category/杂项/
http://ubeni.org/杂项/ (works even without "category/")

Single publish NOT ok:

http://ubeni.org/杂项/穿得美美滴慢跑/

Tag link NOT ok:

http://ubeni.org/tag/服装/

Tag link if ok if in British!:

http://ubeni.org/tag/tgc/

Why this sporadic trouble with utf-8 figures within the permalink? I figured this is normal right now in version 3.3.one of the software!?

Platform is Apache2/PHP5.8 latest.

I certainly need this permalink structure because it makes most semantic sense. It creates my other blogs similar to this Japanese one: http://fujikosuda.com/worklife-jp/ワークスタイル/仕事の将来/サステナビリティ活動の具体的な、測定できる目

So what is the problem?

I realize Chinese text within the URl itself is going to be Search engine optimization friendly. Much appreciate any ideas, help, pointers.

Thanks!