The reason for this: The bnx2 kernel module does not comply with Debians Free Software policy, so it has to live in the non-free section.

After installing that package, and finishing the other upgrade stuff I rebooted the machine, but: No network.

In dmesg I found:

11:04:56 kernel: Broadcom Nextreme II Gigabit Ethernet Driver bnx2 v1.7.4 (Feburary 18, 2008)
11:04:56 kernel: bnx2: Can't load firmware file bnx2-06-4.0.5.fw

This message means it can't find the 'bnx2-06-4.0.5.fw' file in the initrd.img file.

initrd.img is a gzipped cpio archive. At boot time, before the normal root file system is mounted, the kernel unpacks that archive into RAM disk, mounts and uses it as initial root file system. If you'd like to see the contents of a initrd file:
 zcat /boot/initrd.img-2.6.26-1-amd64  | cpio -t

The initrd.img files are built by 'update-initramfs'.

I found that 'bnx2-06-4.0.5.fw' file couldn't be found in the initrd.img file, because the firmware-bnx2 package did not build it. Yes, it built the '/boot/initrd.img-2.6.26-1-amd64' file, but the Xen kernel uses '/boot/initrd.img-2.6.26-1-xen-amd64'!

This problem goes away if you build all the initrd.img files manually:

update-initramfs -k all -u