My apologies for the delayed reply. I can no longer run tests on the PC on which the problem first occurred. The printer driver update was essential, so I chose to upgrade the PC from 8.04 LTS (Hardy) to 8.10 (Intrepid). The following results are from another PC that runs 8.04 LTS.

I must make a note here: The machine where the error first occurred was running 8.04 LTS (Hardy), but it had originally been installed using Ubuntu 6.06LTS (Dapper Drake). It was later migrated to Hardy. This might possibly affect the package conflict resolution settings used by aptitude.

In the coming days, I will try to recreate the same configuration on another machine, and then repeat the tests below. If the results are any different, I will report them.

In the mean time, here are the results from the other PC.

The result from 'apt-get -s remove hplip hpijs' is:

Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be REMOVED:
  foomatic-db-hpijs hpijs hplip
0 upgraded, 0 newly installed, 3 to remove and 23 not upgraded.
Remv foomatic-db-hpijs [20070813-0ubuntu2]
Remv hpijs [2.8.2+2.8.2-0ubuntu8.1]
Remv hplip [2.8.2-0ubuntu8.1]

The result from 'aptitude -s remove hplip hpijs' is probably not what you were asking for. Because the flag '--assume-yes' is not given, aptitude proposes many different possible solutions, and asks the user to accept one of them. Example:

:Reading package lists... Done
Building dependency tree       
Reading state information... Done
Reading extended state information      
Initializing package states... Done
Building tag database... Done      
The following packages are BROKEN:
  foomatic-db-hpijs 
The following packages will be REMOVED:
  hpijs hplip 
0 packages upgraded, 0 newly installed, 2 to remove and 0 not upgraded.
Need to get 0B of archives. After unpacking 1888kB will be freed.
The following packages have unmet dependencies:
  foomatic-db-hpijs: Depends: hpijs (> 2) but it is not installable
Resolving dependencies...
The following actions will resolve these dependencies:

Remove the following packages:
foomatic-db-hpijs
hal-cups-utils
hplip-data
system-config-printer-common
system-config-printer-gnome
ubuntu-desktop

Score is 464

Accept this solution? [Y/n/q/?] 

I have also tested the same command with the mentioned flag added, like 'aptitude -s remove --assume-yes hplip hpijs'. The result was:

Reading package lists... Done
Building dependency tree       
Reading state information... Done
Reading extended state information      
Initializing package states... Done
Building tag database... Done      
The following packages are BROKEN:
  foomatic-db-hpijs 
The following packages will be REMOVED:
  hpijs hplip 
0 packages upgraded, 0 newly installed, 2 to remove and 0 not upgraded.
Need to get 0B of archives. After unpacking 1888kB will be freed.
The following packages have unmet dependencies:
  foomatic-db-hpijs: Depends: hpijs (> 2) but it is not installable
Resolving dependencies...
The following actions will resolve these dependencies:

Remove the following packages:
foomatic-db-hpijs
hal-cups-utils
hplip-data
system-config-printer-common
system-config-printer-gnome
ubuntu-desktop

Score is 464

The following packages will be automatically REMOVED:
  foomatic-db-hpijs hal-cups-utils hplip-data system-config-printer-common 
  system-config-printer-gnome ubuntu-desktop 
The following packages will be REMOVED:
  foomatic-db-hpijs hal-cups-utils hpijs hplip hplip-data 
  system-config-printer-common system-config-printer-gnome ubuntu-desktop 
0 packages upgraded, 0 newly installed, 8 to remove and 0 not upgraded.
Need to get 0B of archives. After unpacking 16.1MB will be freed.
Would download/install/remove packages.