Apparently the isc-dhcp-server is started too early in the boot sequence, it states that it has nothing to do. If I just log directly in as root and start it using the init.d-script, it starts normally.
My setup is basically an utterly standard router, with an eth0 on the inet side, and an eth1 on the lan side. However, I've defined a bridge instead of the eth1 for the lan-side. Thus, the lan-part of the network isn't up until the bridge is up.
I currently believe that the dhcp server is brought up before the bridge is brought up, probably because the bridge is brought up with the 'networking' task, while the eth's are taken up with the 'network-interface' tasks - which are run earlier. (also, the bridge takes a small age to get up compared to the eth's).
If I do take away the bridge config, instead using eth1 directly for the lan side, things work. (However, judging by syslog, things are still tight.)
Ideas of how the get DHCP to start later?
(The reason for the bridge, is to be able to use KVM with bridged networking..)