Okay, make sure brain is in gear before engaging fingers.
I've figure this thing out.
When you have successfully installed packages that form a "Task", that "task" will always show up as selected [*] on the tasksel main menu. If you de-select it, tasksel assumes you want to remove the packages associated with that "task"
In my case, whenever I de-selected the DNS Server option on the main menu, it removed the bind9 package since bind9 IS the dns server package.
This is not a bug. It is by design.