さくらインターネットからSharkSpaceに移行するのに一番の問題がMySQLでした．MySQLは4.0と4.1とで文字の扱いが大きく変わっています．また，MySQLの文字の問題は環境によって様々なケースがあり，これをすれば良いという解決方法がありません．きちんと現状を把握して，それぞれの環境に合わせて解決するしかありません．詳しくは日本MySQLユーザ会のWikiを参照してください．ここではMySQL-4.0, 3.X を現在運用しているひとは原則今のままキープ，と言われてしまっています．
色々試行錯誤の結果，私の場合は，”さくらのレンタルサーバで MySQL 4.0 から 5.1 へ移行した記録”が参考になりました．以下に手順を書きます．
まず，私の場合，MySQL4.0の設定はujisでしたが，データ自体はutf8にしていました．そのため，データをそのまま取得する必要があります．そこで，敢えて5.xのmysqldump を使い，–default-character-set=utf8を指定することでうまくいきました．mysqldump-4.0はutf8に対応していないため，5.xのを使う必要があります．実行時に一つ文句を言ってきましたが，問題はないようです．
$ mysqldump --user=user --password=pass --host=db --default-character-set=utf8 dbname > dump
次にdumpファイルの中に記述されている以下の行をsedなどで全部除きます．
SET @saved_cs_client = @@character_set_client;
SET character_set_client = @saved_cs_client;
その後，dumpファイルの最初に以下の行を加えました．これでdumpをリストアするときの環境をutf8にしてくれます．
SET names utf8;
ここまで準備できたら，SharkSpaceのcPanelでデータベースの設定をします．cPanelは日本語化されているのでやり方はすぐわかると思います．Panel内にデータベースの項目がありますので，そこでデータベースとデータベース用ユーザを作成し，ユーザに権限を与えれば良いです．データベースはusername_hogeというデータベース名であればいくらでも作れます．
また，phpMyAdminで作成したデータベースを選択し，操作 -> 照合順序のところで utf8_general_ci を選択しておきました．
最後にsshでアクセスして，mysqlコマンドでリストアすればOKでした．
$ mysql --user=user --password=pass --host=host dbname < dump