Hmm, I think I got a similar problem:

===
Setting up mysql-server-5.0 (5.0.51a-1ubuntu1) ...
 * Stopping MySQL database server mysqld                                        /usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
                                                                         [ OK ]
Reloading AppArmor profiles : done.
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
 * Starting MySQL database server mysqld                                        /usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
/usr/sbin/mysqld: error while loading shared libraries: /lib/tls/i686/cmov/libc.so.6: cannot apply additional memory protection after relocation: Permission denied
                                                                         [fail]
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.0 (--configure):
 subprocess post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.0; however:
  Package mysql-server-5.0 is not configured yet.
dpkg: error processing mysql-server (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 mysql-server-5.0
 mysql-server
E: Sub-process /usr/bin/dpkg returned an error code (1)
===

I'm on a persistent LiveUSB of Xubuntu 8.04 Alpha 5.

'sudo aa-complain /usr/sbin/cupsd/' did nothing, 'sudo aa-complain /usr/sbin/cupsd' didn't work.

Though I'd very much like a fix or workaround, this is peanuts compared to the hassle it was to get a Feisty LiveUSB persistent ;-)