Try starting bind with AppArmor off. If that works, you're probably experiencing this bug, like myself. Another hint would be a line like this in /var/log/syslog:
Dec 23 02:27:15 Pantheon kernel: [10704.337741] type=1503 audit(1261549635.405:346): operation="inode_permission" requested_mask="::r" denied_mask="::r" fsuid=116 name="/etc/ssl/openssl.cnf" pid=1383 profile="/usr/sbin/named"
You can try clearing the AppArmor cache directory (/etc/apparmor.d/cache), touching /etc/apparmor.d/usr.sbin.named, and making sure bind's apparmor config (/etc/apparmor.d/usr.sbin.named) contains the following:
None of this worked for me, however. Even putting usr.sbin.named into the force-complain directory (where rules are only supposed to be noted, not enforced) and rebooting did not allow bind to run. The configuration is correct, but apparmor is still managing to enforce old, outdated configuration that prevents the new bind from running.
Until version 2.3.1+1403-0ubuntu27.3 of apparmor (karmic-proposed, urgency=low) hits the repositories, or unless you enable proposed updates, all you can do is disable apparmor.