とりあえず 4.1.1-alpha の動作を試してみました。

1.MySQL 4.1.1-alpha
  ./configure --with-charset=utf8 --with-extra-charsets=complex

2.server ujis, client sjis にするとき
  (1) 初期作業
      my.cnf へ次の指定を行います。
        [mysqld]
        default-character-set=ujis
      以後は通常の初期作業 (mysql_install_db, mysqld start, GRANT) を行います。
      mysql コマンドでテスト用データベースとテーブルを作成します。

  (2) ODBC
      MyODBC-3.51.11-2 をインストールします。
      データソース設定を行います。このとき、Initial Statement に
      SET CHARACTER SET SJIS を記述しておきます。

3.server utf8, client utf8 にするとき
  (1) 初期作業
      my.cnf へ次の指定を行います。
        [mysqld]
        default-character-set=utf8
      後は同じです。

  (2) ODBC
      Initial Statement に SET CHARACTER SET UTF8 を記述しておきます。
      後は同じです。

4.Access2000 で動作確認
  リンクテーブルを作成して、実際にレコードを入力してみます。
  UTF8 を指定したときは Windows 機種依存文字が扱えます。
  Office2000 から内部で扱う文字コードが unicode になりましたが、
  恐らく MySQL server 側の都合で第3水準漢字以上は使えないようです。
  残念ですが、扱える文字範囲は Access2000 と同等ではありません。

こちらでは問題なく動作しますので、どこかで設定を間違えています。
phpMyAdmin で問題なく扱えているなら、間違いなくクライアント側の問題です。
まだ解決されていないなら、上記のような手順で ODBC 再インストールしてみてください。