自己レスです。

ここの回答を参考にパッケージの削除をしようとしましたが結果は、

sudo apt-get remove --purge mysql-server-5.0
パッケージリストを読み込んでいます... 完了
依存関係ツリーを作成しています               
状態情報を読み取っています... 完了
以下のパッケージは「削除」されます:
  mysql-server-5.0*
アップグレード: 0 個、新規インストール: 0 個、削除: 1 個、保留: 0 個。
1 個のパッケージが完全にインストールまたは削除されていません。
この操作後に 85.4MB のディスク容量が解放されます。
続行しますか [Y/n]? Y
(データベースを読み込んでいます ... 現在 115038 個のファイルとディレクトリがインストールされています。)
mysql-server-5.0 を削除しています ...
/etc/lsb-base-logging.sh: line 84: INITOUTPUT: unbound variable
invoke-rc.d: initscript mysql, action "stop" failed.
dpkg: mysql-server-5.0 の処理中にエラーが発生しました (--purge):
サブプロセス pre-removal script はエラー終了ステータス 1 を返しました
/etc/lsb-base-logging.sh: line 84: INITOUTPUT: unbound variable
invoke-rc.d: initscript mysql, action "stop" failed.
/etc/lsb-base-logging.sh: line 84: INITOUTPUT: unbound variable
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: クリーンアップ中にエラーが発生しました:
サブプロセス post-installation script はエラー終了ステータス 1 を返しました
以下のパッケージの処理中にエラーが発生しました:
mysql-server-5.0
E: Sub-process /usr/bin/dpkg returned an error code (1)

となりました。

はじめまして。　私も Ubuntu 初心者で、同じような問題に困っていたのですが、さっきグーグルで対処法を見つけました。下記のサイトをご覧ください。ただし、自己責任でお願いしますね。

https://bugs.launchpad.net/netbook-remix/+bug/291987

私自身で試してみたところ、うまくインストール後のセットアップが出来ました。　ちなみに私は、Ubuntu Netbook Remix を使っています。

こちらの環境ではmysqlのサービスがストップしていなかったのが問題でしたので
/etc/init.d/mysql start
を実行することでパッケージの更新が出来ました