package mysql-server-5.5 5.5.22-0ubuntu1 failed to install/upgrade: subprocess installed post-installation script returned error exit status 1

120610 20:27:15 [Note] Plugin 'FEDERATED' is disabled.
120610 20:27:15 InnoDB: The InnoDB memory heap is disabled
120610 20:27:15 InnoDB: Mutexes and rw_locks use GCC atomic builtins
120610 20:27:15 InnoDB: Compressed tables use zlib 1.2.3.4
120610 20:27:15 InnoDB: Initializing buffer pool, size = 128.0M
120610 20:27:15 InnoDB: Completed initialization of buffer pool
120610 20:27:15 InnoDB: highest supported file format is Barracuda.
InnoDB: Database page corruption on disk or a failed
InnoDB: file read of page 0.
InnoDB: You may have to recover from a backup.
120610 20:27:15 InnoDB: Page dump in ascii and hex (16384 bytes):
[...]
InnoDB: End of page dump
120610 20:27:15 InnoDB: Page checksum 2647458526, prior-to-4.0.14-form checksum 2448222090
InnoDB: stored checksum 3029590750, prior-to-4.0.14-form stored checksum 2448222090
InnoDB: Page lsn 0 44227, low 4 bytes of lsn at page end 44227
InnoDB: Page number (if stored to page already) 0,
InnoDB: space id (if created with >= MySQL-4.1.1 and stored already) 0
InnoDB: Page may be a file space header page
InnoDB: Database page corruption on disk or a failed
InnoDB: file read of page 0.
InnoDB: You may have to recover from a backup.
InnoDB: It is also possible that your operating
InnoDB: system has corrupted its own file cache
InnoDB: and rebooting your computer removes the
InnoDB: error.
InnoDB: If the corrupt page is an index page
InnoDB: you can also try to fix the corruption
InnoDB: by dumping, dropping, and reimporting
InnoDB: the corrupt table. You can use CHECK
InnoDB: TABLE to scan your table for corruption.
InnoDB: See also http://dev.mysql.com/doc/refman/5.5/en/forcing-innodb-recovery.html
InnoDB: about forcing recovery.
InnoDB: Ending processing because of a corrupt database page.
120610 20:27:15 InnoDB: Assertion failure in thread 3078387456 in file buf0buf.c line 3608
InnoDB: We intentionally generate a memory trap.
InnoDB: Submit a detailed bug report to http://bugs.mysql.com.
InnoDB: If you get repeated assertion failures or crashes, even
InnoDB: immediately after the mysqld startup, there may be
InnoDB: corruption in the InnoDB tablespace. Please refer to
InnoDB: http://dev.mysql.com/doc/refman/5.5/en/forcing-innodb-recovery.html
InnoDB: about forcing recovery.
16:27:15 UTC - mysqld got signal 6 ;
This could be because you hit a bug. It is also possible that this binary
or one of the libraries it was linked against is corrupt, improperly built,
or misconfigured. This error can also be caused by malfunctioning hardware.
We will try our best to scrape up some info that will hopefully help
diagnose the problem, but since we have already crashed,
something is definitely wrong and this may fail.

key_buffer_size=16777216
read_buffer_size=131072
max_used_connections=0
max_threads=151
thread_count=0
connection_count=0
It is possible that mysqld could use up to
key_buffer_size + (read_buffer_size + sort_buffer_size)*max_threads = 346063 K bytes of memory
Hope that's ok; if not, decrease some variables in the equation.

Thread pointer: 0x0
Attempting backtrace. You can use the following information to find out
where mysqld died. If you see no messages after this, something went
terribl...

Unfortunately looks like there's some kind of corruption in your InnoDB files, this happened due to an upgrade from a pre MySQL 5.1 version to 5.5 directly.

InnoDB: Database page corruption on disk or a failed
InnoDB: file read of page 0.
InnoDB: You may have to recover from a backup.

Looking at the MySQL forums this is the recommended way to repair this:

Your error log states mysql does have the support it needs to run with innoDB support but you`ve modified the size of the ibdata1 file withouth removing the old file first.

In case you did not have any innodb tables in your mysql installation it`s safe to remove it and restart mysql in order for it to recreate that file.

IF you did have data in innodb tables, you should edit your my.cnf file and restore the size value of the following line to it`s default:
'innodb_data_file_path=ibdata1:200M:autoextend '
// 200M was not the default at installation .

After which you should export the database using mysql_dump or any other export method you prefer, remove the ibdata file, edit my.cnf with new size, restart mysql, import old data and you should be done.

Marking this bug as invalid since it's not related to packaging and it's a database data corruption.