I do have the problem, that even if I uninstall mysql completely and do a restart, it still doesn't install mysql. This is the error I get:

Paketlisten werden gelesen... Fertig
Abhängigkeitsbaum wird aufgebaut
Statusinformationen werden eingelesen... Fertig
Die folgenden zusätzlichen Pakete werden installiert:
  libdbd-mysql-perl libmysqlclient18 mysql-client-5.5 mysql-client-core-5.5 mysql-common mysql-server-5.5 mysql-server-core-5.5
Vorgeschlagene Pakete:
  tinyca mailx
Die folgenden NEUEN Pakete werden installiert:
  libdbd-mysql-perl libmysqlclient18 mysql-client-5.5 mysql-client-core-5.5 mysql-common mysql-server mysql-server-5.5
  mysql-server-core-5.5
0 aktualisiert, 8 neu installiert, 0 zu entfernen und 0 nicht aktualisiert.
Es müssen 26,2 MB an Archiven heruntergeladen werden.
Nach dieser Operation werden 94,2 MB Plattenplatz zusätzlich benutzt.
Möchten Sie fortfahren [J/n]? J
Hole:1 http://de.archive.ubuntu.com/ubuntu/ quantal-updates/main mysql-common all 5.5.28-0ubuntu0.12.10.1 [13,4 kB]
Hole:2 http://de.archive.ubuntu.com/ubuntu/ quantal-updates/main libmysqlclient18 amd64 5.5.28-0ubuntu0.12.10.1 [949 kB]
Hole:3 http://de.archive.ubuntu.com/ubuntu/ quantal/main libdbd-mysql-perl amd64 4.021-1 [97,7 kB]
Hole:4 http://de.archive.ubuntu.com/ubuntu/ quantal-updates/main mysql-client-core-5.5 amd64 5.5.28-0ubuntu0.12.10.1 [1.941 kB]
Hole:5 http://de.archive.ubuntu.com/ubuntu/ quantal-updates/main mysql-client-5.5 amd64 5.5.28-0ubuntu0.12.10.1 [8.332 kB]
Hole:6 http://de.archive.ubuntu.com/ubuntu/ quantal-updates/main mysql-server-core-5.5 amd64 5.5.28-0ubuntu0.12.10.1 [5.983 kB]
Hole:7 http://de.archive.ubuntu.com/ubuntu/ quantal-updates/main mysql-server-5.5 amd64 5.5.28-0ubuntu0.12.10.1 [8.842 kB]
Hole:8 http://de.archive.ubuntu.com/ubuntu/ quantal-updates/main mysql-server all 5.5.28-0ubuntu0.12.10.1 [11,6 kB]
Es wurden 26,2 MB in 1 min 5 s geholt (399 kB/s)
Vorkonfiguration der Pakete ...
Vormals nicht ausgewähltes Paket mysql-common wird gewählt.
(Lese Datenbank ... 68073 Dateien und Verzeichnisse sind derzeit installiert.)
Entpacken von mysql-common (aus .../mysql-common_5.5.28-0ubuntu0.12.10.1_all.deb) ...
Vormals nicht ausgewähltes Paket libmysqlclient18:amd64 wird gewählt.
Entpacken von libmysqlclient18:amd64 (aus .../libmysqlclient18_5.5.28-0ubuntu0.12.10.1_amd64.deb) ...
Vormals nicht ausgewähltes Paket libdbd-mysql-perl wird gewählt.
Entpacken von libdbd-mysql-perl (aus .../libdbd-mysql-perl_4.021-1_amd64.deb) ...
Vormals nicht ausgewähltes Paket mysql-client-core-5.5 wird gewählt.
Entpacken von mysql-client-core-5.5 (aus .../mysql-client-core-5.5_5.5.28-0ubuntu0.12.10.1_amd64.deb) ...
Vormals nicht ausgewähltes Paket mysql-client-5.5 wird gewählt.
Entpacken von mysql-client-5.5 (aus .../mysql-client-5.5_5.5.28-0ubuntu0.12.10.1_amd64.deb) ...
Vormals nicht ausgewähltes Paket mysql-server-core-5.5 wird gewählt.
Entpacken von mysql-server-core-5.5 (aus .../mysql-server-core-5.5_5.5.28-0ubuntu0.12.10.1_amd64.deb) ...
Trigger für man-db werden verarbeitet ...
mysql-common (5.5.28-0ubuntu0.12.10.1) wird eingerichtet ...
Vormals nicht ausgewähltes Paket mysql-server-5.5 wird gewählt.
(Lese Datenbank ... 68251 Dateien und Verzeichnisse sind derzeit installiert.)
Entpacken von mysql-server-5.5 (aus .../mysql-server-5.5_5.5.28-0ubuntu0.12.10.1_amd64.deb) ...
Vormals nicht ausgewähltes Paket mysql-server wird gewählt.
Entpacken von mysql-server (aus .../mysql-server_5.5.28-0ubuntu0.12.10.1_all.deb) ...
Trigger für man-db werden verarbeitet ...
Trigger für ureadahead werden verarbeitet ...
libmysqlclient18:amd64 (5.5.28-0ubuntu0.12.10.1) wird eingerichtet ...
libdbd-mysql-perl (4.021-1) wird eingerichtet ...
mysql-client-core-5.5 (5.5.28-0ubuntu0.12.10.1) wird eingerichtet ...
mysql-client-5.5 (5.5.28-0ubuntu0.12.10.1) wird eingerichtet ...
mysql-server-core-5.5 (5.5.28-0ubuntu0.12.10.1) wird eingerichtet ...
mysql-server-5.5 (5.5.28-0ubuntu0.12.10.1) wird eingerichtet ...
AppArmor parser error for /etc/apparmor.d/usr.sbin.mysqld in /etc/apparmor.d/usr.sbin.mysqld at line 9: >>abstractions/mysql<< konnte nicht ge?ffnet werden
start: Job failed to start
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: Fehler beim Bearbeiten von mysql-server-5.5 (--configure):
 Unterprozess installiertes post-installation-Skript gab den Fehlerwert 1 zurück
dpkg: Abhängigkeitsprobleme verhindern Konfiguration von mysql-server:
 mysql-server hängt ab von mysql-server-5.5; aber:
  Paket mysql-server-5.5 ist noch nicht konfiguriert.

dpkg: Fehler beim Bearbeiten von mysql-server (--configure):
 Abhängigkeitsprobleme - verbleibt unkonfiguriert
Trigger für libc-bin werden verarbeitet ...
ldconfig deferred processing now taking place
Es wurde kein Apport-Bericht verfasst, da die Fehlermeldung darauf hindeutet, dass dies lediglich ein Folgefehler eines vorherigen Problems ist.
       Fehler traten auf beim Bearbeiten von:
 mysql-server-5.5
 mysql-server
E: Sub-process /usr/bin/dpkg returned an error code (1)

Do you have any clue, whats going on here?