Did you follow the upgrade guide(s), in most cases an SQL upgrade script needs to be run between upgrading versions. Maybe you missed one of those scripts? Might also be useful to mention which database engine you are on (Oracle, MySQL, PostgreSQL).
Regards Robin
Board member, eZ Publish Community Project Board - Member of the share.ez.no team - Key values: Openness and Innovation.
The upgrade check output should be in a form that you can run as a query in something like phpmyadmin to bring the database up to date. Did you say that would not work though? Can you verify that the script is being run, and if it returns any error messages from the query?