My Opinions

Then I tried aptitude (Version: 0.6.2.1-2), which proposes a solution with these characteristics:

0 packages upgraded, 2 newly installed, 170 to remove and 345 not upgraded.

Here too, you can find the full solution, as well as the data to reproduce this upgrade scenario online at the Mancoosi Debian DUDF repository.

Since this solution was not good either (in particular, it wants to autoremove a lot of stuff, and I do not have time to see whether really all of the 170 packages to remove are needed or not), I resorted to apt-mancoosi (see the Mancoosi software page) which gave me a solution, which I finally liked better

new: 2
removed: 0
replaced: 0
upgraded: 0
downgraded: 0
unsatisfied recommends:: 79
changed: 2
uptodate: 2674
notuptodate: 373

apt-get -s install mew-bin=1:6.3-2 mew=1:6.3-2

You can see just above the apt-get line generated by apt-mancoosi for implement this solution, but calling apt-get this way is not guaranteed to give the expected result: apt-get tries to recompute another solution first, and in this case apt-get, even with this command line, insists in removing stuff, so I resorted to manually downloading and installing these two packages.

We need to find a way to have apt-get or aptitude or some other package manager to apply a solution, when it is complete, like in this case.

For reference, the relevant part of the trace is copied below

sudo apt-get --download-only install mew-bin=1:6.3-2 mew=1:6.3-2 
<snip>
The following extra packages will be installed:
 hyperestraier libestraier8 libfcgi0ldbl libqdbm14 libruby1.8 libsqlite3-ruby libsqlite3-ruby1.8 mew
 mew-bin ppthtml stunnel4 xlhtml
Suggested packages:
 compface x-face-el mu-cite mule-ucs namazu2 namazu2-index-tools mhc logcheck-database
The following packages will be REMOVED:
 irb1.8 libreadline-ruby1.8 rdoc1.8 rubygems1.8
The following NEW packages will be installed:
 hyperestraier libestraier8 libfcgi0ldbl libqdbm14 libsqlite3-ruby libsqlite3-ruby1.8 mew mew-bin
 ppthtml stunnel4 xlhtml
The following packages will be upgraded:
 libruby1.8
1 upgraded, 11 newly installed, 4 to remove and 368 not upgraded.
Need to get 4,160kB of archives.
After this operation, 5,833kB of additional disk space will be used.
Do you want to continue Y/n? Y
Get:1 http://ftp.fr.debian.org squeeze/main stunnel4 3:4.29-1 150kB
Get:2 http://ftp.fr.debian.org squeeze/main libqdbm14 1.8.77-3.1 147kB
Get:3 http://ftp.fr.debian.org lenny/main libestraier8 1.4.9-1.4 130kB
Get:4 http://ftp.fr.debian.org squeeze/main libfcgi0ldbl 2.4.0-8 282kB
Get:5 http://ftp.fr.debian.org lenny/main hyperestraier 1.4.9-1.4 512kB
Get:6 http://ftp.fr.debian.org squeeze/main libruby1.8 1.8.7.302-2 1,965kB
Get:7 http://ftp.fr.debian.org squeeze/main libsqlite3-ruby1.8 1.2.4-2.1 51.5kB
Get:8 http://ftp.fr.debian.org squeeze/main libsqlite3-ruby 1.2.4-2.1 4,094B
Get:9 http://ftp.fr.debian.org squeeze/main mew-bin 1:6.3-2 56.5kB
Get:10 http://ftp.fr.debian.org squeeze/main mew 1:6.3-2 791kB
Get:11 http://ftp.fr.debian.org lenny/main ppthtml 0.5.1-6 18.5kB
Get:12 http://ftp.fr.debian.org lenny/main xlhtml 0.5.1-6 52.6kB
Fetched 4,160kB in 6s (689kB/s)                                                                         
Download complete and in download only mode
sudo dpkg -i /var/cache/apt/archives/mew*
Selecting previously deselected package mew.
(Reading database ... 364432 files and directories currently installed.)
Unpacking mew (from .../archives/mew_1%3a6.3-2_all.deb) ...
Selecting previously deselected package mew-bin.
Unpacking mew-bin (from .../mew-bin_1%3a6.3-2_i386.deb) ...
Setting up mew-bin (1:6.3-2) ...
Processing triggers for man-db ...
Setting up mew (1:6.3-2) ...
<snip>