I'm not sure about your package management issues but wanted to point out that the docs Say that you should completely reload your data using mysqldump when upgrading from a previous minor version. So once you have your complete mysqldump w/ --all-databases --events --routines, be sure to import that into the new binaries.

The reason for the discrepancy is obvious.

When you run

SELECT A.*,B.* FROM (SELECT VERSION() MySQLVersion) A,
(SELECT COUNT(1) MySQLProcColumns FROM information_schema.columns
WHERE table_schema='mysql' AND table_name='proc') B;

you get

mysql> SELECT A.*,B.* FROM (SELECT VERSION() MySQLVersion) A,
    -> (SELECT COUNT(1) MySQLProcColumns FROM information_schema.columns
    -> WHERE table_schema='mysql' AND table_name='proc') B;
+-----------------------+------------------+
| MySQLVersion          | MySQLProcColumns |
+-----------------------+------------------+
| 5.0.51a-community-log |               16 |
+-----------------------+------------------+
1 row in set (0.54 sec)

mysql>

and

mysql> SELECT A.*,B.* FROM (SELECT VERSION() MySQLVersion) A,
    -> (SELECT COUNT(1) MySQLProcColumns FROM information_schema.columns
    -> WHERE table_schema='mysql' AND table_name='proc') B;
+--------------+------------------+
| MySQLVersion | MySQLProcColumns |
+--------------+------------------+
| 5.5.8-log    |               20 |
+--------------+------------------+
1 row in set (0.01 sec)

mysql>

Here is a quick-and-dirty way to fix mysql.proc. Please pay attention:

STEP 01 : On the Slave DB Server, run STOP SLAVE;

STEP 02 : Install MySQL 5.5.26 on a Staging DB Server

STEP 03 : Copy the following files from that Staging DB Server to the Slave DB Server

• /var/lib/mysql/mysql/proc.frm
• /var/lib/mysql/mysql/proc.MYD
• /var/lib/mysql/mysql/proc.MYI

STEP 04 : On the Slave DB Server, run FLUSH TABLES;

STEP 05 : Dump the Stored Procedures on the Master DB Server

MYSQLDUMP_OPTIONS="--routines --no-data --no-create-info --all-databases"
mysqldump -uroot -p ${MYSQLDUMP_OPTIONS} > StoredProc.sql

STEP 06 : Move StoredProc.sql from Master DB Server to /root on the Slave DB Server

STEP 07 : On the Slave DB Server, load the Stored Procedures

mysql -uroot -p -A < /root/StoredProc.sql

STEP 08 : On the Slave DB Server, run START SLAVE;

You should never encounter this issue any more.

Give it a Try !!!

UPDATE 2013-04-22 12:45 EDT

Please run this query

SELECT COUNT(1) FROM information_schema.columns
WHERE table_schema='mysql' AND table_name='user';

For MySQL 5.0, you should get 37. For MySQL 5.5, you should get 42.

If you get 37 on the MySQL 5.5. server, go ahead with running mysql_upgrade.

If you get 42, run my original answer to fix mysql.proc.