phpinfoを見ても

  --enable-mbstring 付き
  Multibyte (Japanese) Support もOK

原因

  --enable-mbregex 付きで configure されていない．

詳細

  --enable-mbstring
    mb_strlen()
    mb_strpos()
    mb_strrpos
    mb_substr()
  --enable-mbregex
    mb_ereg()
    mb_eregi()
    mb_ereg_replace()
    mb_eregi_replace()
    mb_split

現行の PHP4.3.3-1 の Debianパッケージのマルチバイト対応状況

  --enable-mbstring のみ付いている為，mb_str* しか使用できない．
  --enable-mbregex 付きで再コンパイルするしかない．

Reference

  [PHP-users 13906] Re: マルチバイト対応：mb_eregの未定義エラーについて
  http://ns1.php.gr.jp/pipermail/php-users/2003-March/014438.html