FancyURLモードの事を全然考えていませんでした。すいません。
バージョン0.2＋FancyURLの場合は以下の対策をお願いします。

基本の下準備：
http://wa.otesei.com/item/246
に書いて頂いている通りです。

プラグインファイル修正：
以下の通りgetNoDecodeQueryという名前のfunctionをそっくり入れ替えてください。

    function getNoDecodeQuery($q){
        global $CONF;

        if ($CONF['URLMode'] == 'pathinfo'){
            $urlq = serverVar("REQUEST_URI");
            $tempq = explode($q.'/', $urlq, 2);
            if($tempq[1]){
                $tagq = explode('/', $tempq[1]);
                return $tagq[0];
            }
        }else{
            $urlq = serverVar("QUERY_STRING");
            $urlq = str_replace('?','',$urlq);
            $urlq = explode('&',$urlq);
            for($i=0;$i<count($urlq);$i++){
                $tempq = explode('=',$urlq[$i]);
                if($tempq[0] == $q)
                    return $tempq[1];
            }
        }
        return FALSE;
    } 

補足説明：
タグはエンコードしてurlになりますが、$_GETとか$_SERVER['PATH_INFO']などで取得してしまうとphpが自動でデコードしてしまいます。
AND検索、OR検索では「今のurlにエンコードしたタグを追加してリンクを生成」したいので、生の、デコードされていないクエリを取得するにはREQUEST_URIを使わないといけません、なのです。

ついでにここで言うのも何ですが、将来的にjavascriptで何らかのワザを使うときに利用しやすいように、urlには常にUTF-8のrawurlencodeを使用しています。
(ですからEUC-JP利用の際は自動デコード日本語文字列は当然文字化けです)