WP 2.7 already has support for changing permalinks of categories and tags. For example you can use "topics" for categories and your permaling would look like "http://example.org/topics/uncategorized/".
What I'm missing is the support for changing permalinks for pagination of posts, for example if I'm using WP in language other than English, it would be great to replace "page" in "http://example.org/page/2/" with something other. The same is with "more" tag in "http://example.org/cat/2009/post/#more-123". I am trying fully customize WP for my native language.
Oh, and sorry for my poor English.