「カテゴリー」のカテゴリスラッグ欄を変更しても反映されません

カテゴリーを削除して再度つくるということでしか解決せず！

おそらくは、データベースの情報がどこか不正になっていたのだと思います。

他の可能性としては、スラッグに使えない文字を入れたとか、(いわゆる) 全角英数字をいれてしまっていたと思われます。

スラッグに使えない文字 (プラス記号とかスラッシュとか) を入れた場合、それを除去した文字列がスラッグとして使われます。もし、全部使えない文字の場合は、カテゴリー名を URL エンコードした文字列 （文字化けじゃなくて、URL エンコードというものです) になります。

英数字を (いわゆる) 全角で入れてしまった場合は、その全角文字列を URL エンコードしたものがスラッグになります。フォントによっては、全角・半角の区別がつきにくいですから、全角で入れていた可能性もあると思います。

http://www.mydomain.com/category/service

おそらく URL の例示でしょうが、こういう場合は example.com, example.jp などを使いましょう。mydomain.com は実在のドメイン名ですので、あなたがこれを所有しているのでない限り、勝手に使うのは避けるべきです。