MySQL 5.1.36 is now available on Dotdeb for Debian 4.0 “Etch” / Debian 5.0 “Lenny” in amd64/i386 flavours.
It fixes a lot of annoying bugs (read the list of changes to be convicted), especially one about granting the right privileges during the Debian post-installation process. The mysql-server-5.1 package should now install without needing any ugly trick.
Please upgrade your servers.