package mysql-server-5.1 5.1.41-3ubuntu12.3 failed to install/upgrade: Package is in a very bad inconsistent state - you should reinstall it before attempting a removal.

Upon trying to install/upgrade/remove any package with apt-get, it fails with this error. Every time this happens, I either have to quit with Ctrl+C, or it simply fails by itself.

ProblemType: Package
DistroRelease: Ubuntu 10.04
Package: mysql-server-5.1 5.1.41-3ubuntu12.3
ProcVersionSignature: Ubuntu 2.6.32-24.38-generic 2.6.32.15+drm33.5
Uname: Linux 2.6.32-24-generic i686
NonfreeKernelModules: nvidia
AptOrdering:
 mysql-server-5.1: Purge
 man-db: Configure
Architecture: i386
Date: Sun Aug 15 05:24:50 2010
ErrorMessage: Package is in a very bad inconsistent state - you should reinstall it before attempting a removal.
InstallationMedia: Ubuntu 10.04 LTS "Lucid Lynx" - Release i386 (20100429)
Logs.var.log.daemon.log:

Logs.var.log.kern.log:

MySQLConf.etc.mysql.conf.d.mysqld.safe.syslog.cnf:
 [mysqld_safe]
 syslog
MySQLVarLibDirListing: ['ib_logfile1', 'ibdata1', 'mysql_upgrade_info', 'mysql', 'debian-5.1.flag', 'ib_logfile0']
SourcePackage: mysql-dfsg-5.1
Title: package mysql-server-5.1 5.1.41-3ubuntu12.3 failed to install/upgrade: Package is in a very bad inconsistent state - you should reinstall it before attempting a removal.