Support

No, this is not a bug, it's the intended mode of operation. Since the URL Redirection tool can be used to redirect to external sites we can not pass the URL through the Joomla! router to turn it into a SEF URL. AFAIK this problem only happens if you use the core SEF feature of Joomla!, but not if you use any third party SEF extension. The reason is an oversight in Joomla!, which doesn't try to enforce canonical URLs, i.e. it won't try to create SEF URLs automatically from plain (messy) URLs.

There are no plans to change that behaviour of the URL redirection system, as it would break redirections to external URLs.

And just a final note. Your URLs will not really change even if your category names change! This is a Joomla! hidden feature. The router actually looks only at the numeric portion of the last parameter in order to determine the ID of the item to load. Anything before that is silently ignored. Even the alpha portion of the URL is ignored. For all Joomla! cares, http://www.example.com/something/1-somewhere/2-else/3-hello-world, http://www.example.com/something/1-somewhere/2-else/3-this-is-ignored and http://www.example.com/something/lets-write-something-silly/i-like-ice-tea/3-woot are all the same. Funny, huh? :)