update-rc.d: warning: /etc/rc2.d/K09samba is not a link to ../init.d/samba or /etc/init.d/samba
update-rc.d: warning: /etc/rc3.d/K09samba is not a link to ../init.d/samba or /etc/init.d/samba
invoke-rc.d: dangling symlink: /etc/rc2.d/K09samba
The rc2.d and rc3.d links actually point to /samba for some reason. So I removed the symlinks and the installation went through.
The package installed was (3.0.28a-1ubuntu4.5). There's a similar issue reported on Debian sid for samba 3.0.26a-1.