Finally, phpMyAdmin packages for Debian and Ubuntu do not lag much behind upstream. Today, I've prepared packages for yesterday released bug fix release 3.5.6.
For Debian users, the package should be soon available in experimental (sorry no uploads to unstable during freeze).
Ubuntu users, can use my phpMyAdmin PPA. After dozens of comments and no help offered, I've still decided to be nice to Ubuntu users and adjusted the package so that it should work on Lucid as well. The downside is that, unlike in Debian, the package includes bundled copy of many PHP and javascript libraries.
PS: As soon as Debian is not frozen or 4.0 is officially released, I will start uploading 4.0 to experimental. My current bet is that 4.0 release will come earlier.