『MagicalURL』と勝手に名付けた、urlカスタマイズの一例がありましたが、url生成はコアファイル改造じゃなくって、プラグインで実現できました。
(とは言っても激しくつまらない中身ですが〜)

ダウンロード：NP_MagicalURL050.zip ※配布停止中

使用上の必須条件は、
1)Nucleus Ver.3.22 ＋　ここの修正。
【追記：このNP_MagicalURLを使う限りは別に修正しなくても大丈夫だと思う】
2)FancyURL正常動作確認済み。
3).htaccessにてmod_rewriteモジュール使用が許可されている
となります。

使い方：
1)まず、.htaccessに、解凍後できたsample.htaccessの中身をコピペ。
2)次に、fancyurls.config.phpの後半部分は、同じく解凍後できたsample.fancyurls.config.phpの後半部分へと変更
3)プラグインのインストール、で完了。

注意点：
urlに登場する「blogid」とか「archivelist」とかは、fancyurls.config.phpの後半部分で定義されています。
これを変更すれば自動生成されるURLに反映されますが、当然、mod_rewriteのルールも合わせて自分で変更する必要がありますので忘れずに。

ちなみに、おさらいは↓。
1)Normal Mode
　http://****.com/index.php?catid=2&blogid=1
2)FancyURL Mode
　http://****.com/category/2/blogid/1
3)MagicalURL Mode
　http://****.com/catid_2_blogid_1.html

サブカテゴリとかtagとかの場合【追記】
まだ検証していないですが、404エラーになったページのurlを眺めつつ、.htaccessのmod_rewriteルールを増やしていけばいいだけだと思います。
(lolipopみたいに404ページがリダイレクトされちゃうサーバはやりにくいけどね...頭の体操して下さい)
で、こんな行を増やしました、という報告をコメントでもTBでもいただければ幸いです。



【2006-03-22 19:18追記】
動作確認/その他微調整に関するまとめ情報は↓参照！

NP_Magical真の解決？ - 備忘録とかもろもろ

"色々問題のあったNP_Magicalもなんとかなりそうなのでまとめ記事を。"