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).
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.