can't insall mysql-server after upgrade to debian wheezy

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
...
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) ...
[FAIL] Starting MySQL database server: mysqld . . . . . . . . . . . . . . failed!
invoke-rc.d: initscript mysql, action "start" failed.
...
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)
$ 

(Full output at http://pastebin.com/7WpSEDbx)

Notice the somewhat worrying gdbm fatal: malloc error.

How do I get mysql back?