1. I've installed a fresh version of Ubuntu 10.04 64bit, I didn't install bind when choosing what packages should be installed in the Ubuntu installer.

2. I downloaded the auto installer for Plesk 10.1 and installed it successfully.

3. When I logged into the Plesk control panel and tried to change the password, it failed because it couldn't restart bind.

I SSH'd into the box and tried a sudo /etc/init.d/bind9 restart and get the following:

brad@ws01:/root# sudo /etc/init.d/bind9 restart
 * Stopping domain name service... bind9                                                                                                                                                                WARNING: key file (/etc/bind/rndc.key) exists, but using default configuration file (/etc/bind/rndc.conf)
rndc: connect failed: 127.0.0.1#953: connection refused
named: no process found                                   [ OK ]
 * Starting domain name service... bind9                  [fail]

Looking at tail /var/log/messages reveals a whole bunch of:

Feb 23 16:08:21 ws01 kernel: [ 3840.065851] type=1503 audit(1298441301.831:31):  operation="open" pid=5565 parent=5563 profile="/usr/sbin/named" requested_mask="::r" denied_mask="::r" fsuid=108 ouid=0 name="/var/named/run-root/etc/named.conf"

Edit:

After following ooshro's advice, bind runs, however I still get the named: no process found error:

brad@ws01:/etc/apparmor.d$ sudo /etc/init.d/bind9 restart
 * Stopping domain name service... bind9
WARNING: key file (/etc/bind/rndc.key) exists, but using default configuration file (/etc/bind/rndc.conf)
named: no process found                    [ OK ]
 * Starting domain name service... bind9   [ OK ]