Ubuntu – Installing clean Trusty Tar with MySQL 5.6 might contain corrupt package

I tried to install mysql-server-5.6 on my vagrant box ubuntu/trusty64
It however works with this box. Besides other sources.list I cant spot a difference. But I wonder why this error occurs, since the first box is the official ubuntu image and uses the main sources.list….

sudo apt-get install mysql-server-5.6

Setting up mysql-server-5.6 (5.6.19-0ubuntu0.14.04.1) ...
start: Job failed to start
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing package mysql-server-5.6 (--configure):
 subprocess installed post-installation script returned error exit status 1
Processing triggers for ureadahead (0.100.0-16) ...
E: Sub-process /usr/bin/dpkg returned an error code (1)

Purging and re-installing does not change the output.
Leaving the password for "root" blank, when configuring does not change anything. Manually removing /var/lib/mysql after purging does nothing.
/var/lib/mysql does not seem to exist when setting up a clean install, so this shouldnt be a problem.

/var/log/mysql/error.log is this, but I have no clue what it means:

2015-09-29 18:05:21 6911 [Warning] Using unique option prefix myisam-recover instead of myisam-recover-options is deprecated and will be removed in a future release. Please use the full name instead.
2015-09-29 18:05:21 6911 [Note] Plugin 'FEDERATED' is disabled.
2015-09-29 18:05:21 6911 [Note] InnoDB: Using atomics to ref count buffer pool pages
2015-09-29 18:05:21 6911 [Note] InnoDB: The InnoDB memory heap is disabled
2015-09-29 18:05:21 6911 [Note] InnoDB: Mutexes and rw_locks use GCC atomic builtins
2015-09-29 18:05:21 6911 [Note] InnoDB: Compressed tables use zlib 1.2.8
2015-09-29 18:05:21 6911 [Note] InnoDB: Using Linux native AIO
2015-09-29 18:05:21 6911 [Note] InnoDB: Not using CPU crc32 instructions
2015-09-29 18:05:21 6911 [Note] InnoDB: Initializing buffer pool, size = 128.0M
2015-09-29 18:05:21 6911 [Note] InnoDB: Completed initialization of buffer pool
2015-09-29 18:05:21 6911 [Note] InnoDB: Highest supported file format is Barracuda.
2015-09-29 18:05:21 6911 [Note] InnoDB: 128 rollback segment(s) are active.
2015-09-29 18:05:21 6911 [Note] InnoDB: Waiting for purge to start
2015-09-29 18:05:21 6911 [Note] InnoDB: 5.6.19 started; log sequence number 1626097
ERROR: 1062  Duplicate entry 'innodb' for key 'PRIMARY'
2015-09-29 18:05:21 6911 [ERROR] Aborting

2015-09-29 18:05:21 6911 [Note] Binlog end
2015-09-29 18:05:21 6911 [Note] InnoDB: FTS optimize thread exiting.
2015-09-29 18:05:21 6911 [Note] InnoDB: Starting shutdown...
2015-09-29 18:05:23 6911 [Note] InnoDB: Shutdown completed; log sequence number 1626107
2015-09-29 18:05:23 6911 [Note] /usr/sbin/mysqld: Shutdown complete

This ERROR: 1062 Duplicate entry 'innodb' for key 'PRIMARY' seems to be one cause for the error? I found a bug on the Ubuntu Launchpad but it never got fixed and just "expired".