[debian-mysql] Bug#708049: can't insall mysql-server after upgrade to debian wheezy

[Tzadik Vanderhoof]

Package: mysql-server-5.5
Version: 5.5.30

I upgraded debian to wheezy and got errors with mysql-server so I
removed it. Now I can't reinstall it. I get:

$ sudo apt-get install mysql-server
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following extra packages will be installed:
  mysql-server-5.5
Suggested packages:
  tinyca
The following NEW packages will be installed:
  mysql-server mysql-server-5.5
0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
Need to get 0 B/2065 kB of archives.
After this operation, 31.6 MB of additional disk space will be used.
Do you want to continue [Y/n]?
Preconfiguring packages ...
Selecting previously unselected package mysql-server-5.5.
(Reading database ... 33290 files and directories currently installed.)
Unpacking mysql-server-5.5 (from
.../mysql-server-5.5_5.5.30+dfsg-1.1_i386.deb) ...
Selecting previously unselected package mysql-server.
Unpacking mysql-server (from .../mysql-server_5.5.30+dfsg-1.1_all.deb) ...
Processing triggers for man-db ...
gdbm fatal: malloc error
Setting up mysql-server-5.5 (5.5.30+dfsg-1.1) ...
[ ok ] Stopping MySQL database server: mysqld.
insserv: warning: script 'K01exim' missing LSB tags and overrides
insserv: warning: script 'K01sendmail' missing LSB tags and overrides
insserv: warning: script 'S16libdevmapper1.02' missing LSB tags and overrides
insserv: warning: script 'exim' missing LSB tags and overrides
insserv: warning: script 'iptables' missing LSB tags and overrides
insserv: warning: script 'sendmail' missing LSB tags and overrides
insserv: warning: script 'apache' missing LSB tags and overrides
insserv: warning: script 'libdevmapper1.02' missing LSB tags and overrides
[FAIL] Starting MySQL database server: mysqld . . . . . . . . . . . .
. . failed!
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.5 (--configure):
 subprocess installed post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.5; however:
  Package mysql-server-5.5 is not configured yet.

dpkg: error processing mysql-server (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 mysql-server-5.5
 mysql-server
E: Sub-process /usr/bin/dpkg returned an error code (1)
$

Notice the somewhat worrying gdbm fatal: malloc error.

How do I get mysql back?