Pos vaya, un bug que es más común de lo que debiera.

Open up Synaptic Package Manager
Settings > Repositories > Other Software, then add the following:
deb http://us.archive.ubuntu.com/ubuntu/ lucid main
“Reload” the package list
Find “pm-utils” then go to Package > Force Version.. and select 1.3.x
Install the downgraded package
Find “pm-utils” again, go to Package > Lock Version

Fuente: Robert Beal