I've been swamped lately, so it took me a bit to get to this one. Mea culpa.
First of all, keep in mind that I haven't ever actually [i]directly[/i] implemented DNS and BIND, though I've set up a couple of blackbox solutions running DNS and done other, similarly related, work. In any case, I don't know much about the specific challenges you'll face in implementing DNS and BIND for your organization, but I can offer some observations based on my theoretical understanding of the needs of such servers.
The first things you need to pay attention to in making this decision are your organization's specific needs, ease of implementation, ease of configuration, and ease of software updating. Since you're talking about running Linux, issues of security and stability are largely secondary, since in general Linux is a fairly secure and stable OS by default. Where that isn't true for specific implementations in some really egregious fashion, however, it pays to take note.
That being the case:
I've seen notable references to SuSE/Novell, Ubuntu, Debian, Fedora, Mandrake, xBSD, Slackware, and Linux From Scratch (LFS).
SuSE rates extremely well in ease of implementation, reasonably well in ease of software updating, and doesn't suffer terrible problems involving security and stability as a dedicated server system. Configuration is decent, and there are tools included by default that should help you with server configuration. Novell integrated networking software solutions are wholly superfluous for your purposes, however. DNS/BIND systems act as servers for [b]other computers[/b], not for application-level operations, and the Novell integrated networking solutions are geared toward users, not computers. The amount of resource overhead and interface abstraction involved in implementing the Novell-carryover solution(s) on top of the basic SuSE Linux OS would be quite counterproductive for a DNS/BIND server setup. Consider the merits of SuSE without Novell's NetWare-derived solutions on top of it. Since SuSE has the above mentioned positive characteristics and includes the KDE GUI in a default install, and since it uses YaST2 to help with more fine-grained software management from the GUI when necessary (which is apparently quite important for your purposes), SuSE Linux is a good option. I'm sure its DNS/BIND implementation is solid though, as I've mentioned, I don't have any experience with it. If you're planning to just turn off X and never use it again after initial implementation and configuration, though, I'd choose something else, as the CLI system administration tools (primarily those related to software management) tend to suck on SuSE.
Ubuntu is, primarily, just Debian with a default GUI setup and some GUI-related user-friendliness integrated. I haven't used it myself (yet), but my discussions with those who have, reading about it, and understanding of the principles addressed by Ubuntu (not to mention the reputation of its creators and maintainers) indicate to me that it is probably a superlative option for those who want something as plain-vanilla Debian as possible with the added value of a lot of attention to detail for the GUI. It is above described as being optimized for desktop use, but the beauty of optimizing Linux (particularly Debian, in my experience) for a particular purpose is that it's trivial to use it for another purpose without any degradation in suitability for that other purpose. In other words, don't let the "optimized for the desktop" idea scare you off: that doesn't mean it's de-optimized for DNS/BIND server use. In fact, the desktop orientation of Ubuntu without reduction in suitability for server uses should be a net gain for your organization, because of the requirement for GUI functionality. Ubuntu should be exceedingly good with ease of implementation, ease of configuration, and ease of software management and updating. It does default to Gnome, however, which is probably less than optimal for you (noting your preference for KDE). Stability and security should be rock solid, particularly considering the close relationship Ubuntu has with Debian Stable. In general, this is a good option to consider for your organization's needs and personal preferences, along with SuSE.
Fedora is, according to Fedora users with whom I've spoken, not nearly as much a "beta test" of RHEL as people seem to think. Those Fedora devotees tend to be quite biased in favor of Fedora, though, so take that with a grain of salt. I'm working with Fedora exclusively at my datacenter job, but as the datacenter technician I pretty much only deal with the command line for minor, routine tasks, and with installation on very much homogenous hardware certified to be RH compatible, so my experience with Fedora is not terribly useful there. I do know that it has options for ease of implementation that should be easier than my favorite (Debian) for those used to the GUI, though it has some quirks for CLI use that require some experience to really get a handle on 'em. Ease of configuration is roughly equivalent to that of SuSE. Software management and updating will likely be marginally less easy at the GUI than with SuSE, though a lot easier at the CLI than SuSE's CLI administration tools (SuSE really is not my favorite at the CLI by any means, and is very clunky to try to wrangle when you aren't using the GUI tools). If you want to try to reach a compromise between GUI and CLI, you could definitely choose worse options than Fedora. Fedora can be slightly flaky in comparison to RHEL, in my experience, so it's not realistically up to the RHEL standard, but if you can implement it successfully you should be able to make good use of it without major issue.
Avoid Mandrake like the plague for server purposes, if you don't have any specific preference for it. Mandrake is the exception to the "you can optimize for one thing without losing suitability for another", generally. In optimizing for end-user desktop performance and user-friendliness, some decisions have been made that make it suboptimal for server-only use. It is, of course, leagues better than Windows for such purposes, and is much closer in server suitability in most implementations to other unices than it is to Windows, but the worst of a good bunch is still not as good as something from the average-or-better range of that same good bunch. If you are comfortable with Mandrake, dislike all other distros, and generally just want to use it, it probably won't hurt anything to do so, but all else being equal I recommend against Mandrake.
Slackware, when properly implemented and configured, is probably about the best server Linux in existence (not counting something even more bare-metal like LFS), right up to the point where you need to start doing any ongoing system administration. At that point, it becomes quite a pain in the arse because it just doesn't include the same ease of maintenance as other distributions like Debian, RHEL/Fedora, and SuSE. It's also not as easily implemented and configured for anyone that isn't essentially a Linux god as the other major distributions. For any kind of corporate environment, I have to recommend against it for reasons that are essentially the diametrical opposite of those I recommend against Mandrake. These two distributions are extremes, where your needs will be closer to the middle. I'm not surprised you've run into issues with it, though the fault is not with Slackware so much as with the fact that the job of system administration on Slackware requires skillsets that just aren't prevalent enough to expect it to be properly managed in a business environment, generally speaking.
Linux From Scratch is great if you want the extremely implementation-specific perfection of a system you built from component bits to do the job at hand. See Slackware re: system administration, though, and double the problem (at least). This is not something I'd use as a DNS/BIND server in a corporate environment if I had [b]any[/b] other option, I think. In fact, it might even be a toss-up between LFS and Windows, just because even if I know what I'm doing, I'll eventually leave and someone else will have to maintain the system when I'm gone.
This leaves Debian (which you've already said you probably don't want to use) and the BSDs. It has been suggested you use FreeBSD, but if you're going to use a BSD, I recommend OpenBSD. It is widely regarded as "the" stable and secure x86-compatible OS, and if you're going to deal with the less-user-friendly-than-Linux issues of BSD anyway, you might as well go with the more server-oriented BSD of the lot. Implementing DNS and BIND on OpenBSD should provide a rock solid, robust, simple solution for you, though you won't have the same ease of system administration that you would with many Linux distributions.
Debian, meanwhile . . .
Obviously, Debian is my favorite. You already know this. This is, in large part, for three reasons:
1. It is very easy to maintain, with the best CLI implementation of software management tools available. This is very, very important for business production environment server systems.
2. It installs cleanly. Even when you tell Fedora to do a "minimal install" with no extra junk, it still installs about half again as much crap as Debian's minimal install. Granted, it's not as clean as LFS, but it's comparable with Slackware in that regard (except that it includes the aforementioned software management system). This is, of course, quite important for server systems.
3. Security and stability are legendary in Linux circles. I don't think any other distribution of Linux has people testing, cross-testing, compatibility testing, and otherwise beating the hell out of software to make sure it'll work properly as thoroughly as Debian's community does these things. As I said earlier, this isn't quite as big a deal as other concerns when you choose a good Linux distribution at all, but it's still one of the reasons I like Debian as much as I do.
That aside, you express concerns with Debian's suitability to the needs of your organization. That's a deal-breaker. If it doesn't fit, don't use it. Before discarding it as being difficult to configure, however, and going after a more kitchen-sink approach to Linux installation and configuration, you might want to take a look at the tasksel option for installing Debian on your system. Using tasksel during installation basically turns Debian into something of a kitchen-sink distro itself, though it still maintains some of its purity of installation in that it still tends to be less bloated and less unwieldy than some other kitchen-sink installations. I don't have a whole lot of experience with tasksel managed implementations of Debian, though, so I can't swear to its suitability much. I used tasksel to set up a desktop system for a friend a few days ago, and it is working beautifully, but one good experience for one end-user doesn't mean much for your purposes.
In any case, whenever you read anyone's recommendations about which distro to use, keep my short list of important considerations in mind and realize that many of the reasons people (myself included) might cite for choosing a particular distribution will be [b]entirely irrelevant[/b] for your purposes. Focus on what's important for your needs, and feel free to disregard the rest.