Apparently it is possible to use Byobu even on Debian. It was to be expected, as it should be fairly distribution-independent. You need to install screen, python-newt and then you can run:
sudo dpkg -i byobu_3.16-0ubuntu1_all.deb
Of course the package has to be downloaded from an Ubuntu mirror first 😉
And the result is:
 oliver@ymir:~$ lsb_release -a No LSB modules are available. Distributor ID: Debian Description: Debian GNU/Linux 5.0.7 (lenny) Release: 5.0.7 Codename: lenny  oliver@ymir:~$ sudo dpkg -l|grep byobu ii byobu 3.16-0ubuntu1 ...
(last line truncated to fit)