I have a clean minimal install of Ubuntu 12.04 LTS server 64-bit (just a root user and nothing alse installed). I tried to install the mysql-server with the following command:

apt-get install mysql-server

The installation aborts with the following error:

The following NEW packages will be installed:
  libdbd-mysql-perl{a} libmysqlclient18{a} mysql-client mysql-client-5.5{a}
  mysql-client-core-5.5{a} mysql-common{a} mysql-server mysql-server-5.5{a}
  mysql-server-core-5.5{a}
0 packages upgraded, 9 newly installed, 0 to remove and 0 not upgraded.
Need to get 11.7 kB/26.2 MB of archives. After unpacking 94.5 MB will be used.
Do you want to continue? [Y/n/?] y
Get: 1 http://mirror.eu.oneandone.net/ubuntu/ubuntu/ precise/main mysql-client all 5.5.22-0ubuntu1 [11.7 kB]
Fetched 11.7 kB in 0s (567 kB/s)
Preconfiguring packages ...
Selecting previously unselected package mysql-common.
(Reading database ... 54008 files and directories currently installed.)
Unpacking mysql-common (from .../mysql-common_5.5.22-0ubuntu1_all.deb) ...
Selecting previously unselected package libmysqlclient18.
Unpacking libmysqlclient18 (from .../libmysqlclient18_5.5.22-0ubuntu1_amd64.deb) ...
Selecting previously unselected package libdbd-mysql-perl.
Unpacking libdbd-mysql-perl (from .../libdbd-mysql-perl_4.020-1build2_amd64.deb) ...
Selecting previously unselected package mysql-client-core-5.5.
Unpacking mysql-client-core-5.5 (from .../mysql-client-core-5.5_5.5.22-0ubuntu1_amd64.deb) ...
Selecting previously unselected package mysql-client-5.5.
Unpacking mysql-client-5.5 (from .../mysql-client-5.5_5.5.22-0ubuntu1_amd64.deb) ...
Selecting previously unselected package mysql-server-core-5.5.
Unpacking mysql-server-core-5.5 (from .../mysql-server-core-5.5_5.5.22-0ubuntu1_amd64.deb) ...
Processing triggers for man-db ...
Setting up mysql-common (5.5.22-0ubuntu1) ...
Selecting previously unselected package mysql-server-5.5.
(Reading database ... 54189 files and directories currently installed.)
Unpacking mysql-server-5.5 (from .../mysql-server-5.5_5.5.22-0ubuntu1_amd64.deb) ...
Selecting previously unselected package mysql-client.
Unpacking mysql-client (from .../mysql-client_5.5.22-0ubuntu1_all.deb) ...
Selecting previously unselected package mysql-server.
Unpacking mysql-server (from .../mysql-server_5.5.22-0ubuntu1_all.deb) ...
Processing triggers for ureadahead ...
Processing triggers for man-db ...
Setting up libmysqlclient18 (5.5.22-0ubuntu1) ...
Setting up libdbd-mysql-perl (4.020-1build2) ...
Setting up mysql-client-core-5.5 (5.5.22-0ubuntu1) ...
Setting up mysql-client-5.5 (5.5.22-0ubuntu1) ...
Setting up mysql-server-core-5.5 (5.5.22-0ubuntu1) ...
Setting up mysql-server-5.5 (5.5.22-0ubuntu1) ...
120502 10:17:41 [Note] Plugin 'FEDERATED' is disabled.
120502 10:17:41 InnoDB: The InnoDB memory heap is disabled
120502 10:17:41 InnoDB: Mutexes and rw_locks use GCC atomic builtins
120502 10:17:41 InnoDB: Compressed tables use zlib 1.2.3.4
120502 10:17:41 InnoDB: Initializing buffer pool, size = 128.0M
120502 10:17:41 InnoDB: Completed initialization of buffer pool
120502 10:17:41 InnoDB: highest supported file format is Barracuda.
120502 10:17:41  InnoDB: Waiting for the background threads to start
120502 10:17:42 InnoDB: 1.1.8 started; log sequence number 1595675
120502 10:17:42  InnoDB: Starting shutdown...
120502 10:17:42  InnoDB: Shutdown completed; log sequence number 1595675
start: Job failed to start
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.5 (--configure):
 subprocess installed post-installation script returned error exit status 1
No apport report written because MaxReports is reached already
                                                              Setting up mysql-client (5.5.22-0ubuntu1) ...
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.5; however:
  Package mysql-server-5.5 is not configured yet.
dpkg: error processing mysql-server (--configure):
 dependency problems - leaving unconfigured
No apport report written because MaxReports is reached already
                                                              Processing triggers for libc-bin ...
ldconfig deferred processing now taking place
Errors were encountered while processing:
 mysql-server-5.5
 mysql-server
E: Sub-process /usr/bin/dpkg returned an error code (1)
A package failed to install.  Trying to recover:
Setting up mysql-server-5.5 (5.5.22-0ubuntu1) ...
start: Job failed to start
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.5 (--configure):
 subprocess installed post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.5; however:
  Package mysql-server-5.5 is not configured yet.
dpkg: error processing mysql-server (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 mysql-server-5.5
 mysql-server

I am completely lost because I have tried everything on the web to solve my problem (clearning the install, reconfiguring with dpkg, manually editing the my.cnf). I also set up a new clean install but nothing helped. What am I doing wrong?

New information: The file /var/log/upstart/mysql.log contains the following error after the installation:

AppArmor parser error for /etc/apparmor.d/usr.sbin.mysqld in /etc/apparmor.d/tunables/global at line 17: Could not open 'tunables/proc'