Ok, got an answer for this one.
Debian Lenny is delivered with bind pre-installed & running
The apt-get remove bind9 that I did was not correct (does't remove bind & less stop the running service)
To correctly remove bind do this
apt-get purge bind9
update-rc.d bind9 remove
apt-get remove bind9 IS NOT SUFFICIENT /INCORRECT
Use code above.
A reboot -n will restart server & get things straight.
There's probably a more graceful way to restart all services, but the reboot did the trick for me.