First, some wishlist suggestions, then the situations that call for them.
IMHO, the wishlist suggestions are listed in decreasing order of
development-effort-required to end-user-benefit ratio:

1.  Rephrase the message "but $OFFENDING_VERSION is to be installed"
in the case where $OFFENDING_VERSION is _already_ installed, and
circumstances (apt-get limitations, version-specific dependencies and
unavailable packages, held packages, to name a few) prevent the offending
package from being downgraded, upgraded, or removed.

This happens if two deb sources in sources.list release newer versions of
packages without monotonically increasing version strings, which in
turn happens when you're testing packages in someone's unofficial
apt archive, and the packages later become official Debian packages.

Some suggested improved diagnostic messages:

	$OFFENDING_VERSION is already installed

	$OFFENDING_VERSION is installed and cannot be upgraded or removed
	without breaking a lot of other dependencies

	$OFFENDING_VERSION may need to be removed/purged and reinstalled

2.  An option which, similar to --reinstall, tells apt-get to perform
the downgrades or remove/purge-then-installs as required to satisfy
dependencies above.

3.  A "dist-downgrade" command, which removes or downgrades any packages
installed on the system that can no longer be downloaded.

Background:

I've seen this kind of thing way too often:

	genki:~# apt-get --reinstall install galeon
	Reading Package Lists... Done
	Building Dependency Tree... Done
	Some packages could not be installed. This may mean that you have
	requested an impossible situation or if you are using the unstable
	distribution that some required packages have not yet been created
	or been moved out of Incoming.

	Since you only requested a single operation it is extremely likely that
	the package is simply not installable and a bug report against
	that package should be filed.
	The following information may help to resolve the situation:

	Sorry, but the following packages have unmet dependencies:
	  galeon: Conflicts: mozilla-browser (>= 2:0.9.4) but 2:0.9.4-1 is to be install
	ed
	E: Sorry, broken packages

The actual preconditions are:

1.  Galeon and various mozilla packages are already installed on the
system, and they are all dependent on exactly version 2:0.9.4-1 of
mozilla-.* and libnspr4.*.

2.  The deb source where these packages were downloaded from has
disappeared.

3.  An earlier version of mozilla.*, and libnspr4.* appeared in the
Debian unstable deb source.  A version of Galeon which depends on these
packages and conflicts with the later versions also appears in unstable.

As a result, apt-get can't install new galeon because it can't figure
out what to do about the old (new) mozilla stuff.

This is not an isolated incident, or at least it is one of many isolated
incidents--to cite an example using the official Debian archive, it also
happened during the great renaming of woody from "unstable" to "testing".
It is now almost a year later and I'm _still_ finding packages on my
systems that can't be upgraded because of package interdependencies.

Hello submitters.

Zygo, your first proposal makes sense and would be good to implement.
Helge, your proposal matches above one.

Zygo, your 2nd and 3rd proposals are 'wontfix', because Debian doesn't support downgrading
officially, therefore apt cannot have 'downgrade' or 'dist-downgrade' option.
Remove/purge+install cannot resolve dependencies better than just upgrading.

Seven years ago, when this bug was filed, remove/purge+install did quite
often resolve dependencies better than just upgrading.  Apt's dependency
resolver at the time was quite limited (or maybe a better word is
"broken") and often was "blinded" by a single conflicting package.
Removing that package allowed apt-get to consider other upgrade plans,
and often those plans included installing the exactly the same package
that was just removed.

Since then the apt tools have improved considerably.  I generally do
dist-upgrades now by first upgrading apt and aptitude, then upgrading
the rest of the system, because each Debian release's aptitude package
has a much better dependency resolver than the previous one.

I generally use aptitude more than apt-get now, although there are still
differences between the two that are useful when one or the other cannot
resolve dependencies in specific situations.

Aptitude's interactive dependency resolver and apt preferences do a
fairly good job at implementing all three proposals, including downgrades.
Although I haven't attempted a full dist-downgrade in years, I have done
downgrades of families of hundreds of packagse (e.g. dependents of perl
and libglib) from Lenny to Etch with aptitude, apt preferences, and a
bit of manual hinting in the dependency resolver.

Seven years ago, when this bug was filed, remove/purge+install did quite
often resolve dependencies better than just upgrading.  Apt's dependency
resolver at the time was quite limited (or maybe a better word is
"broken") and often was "blinded" by a single conflicting package.
Removing that package allowed apt-get to consider other upgrade plans,
and often those plans included installing the exactly the same package
that was just removed.

Since then the apt tools have improved considerably.  I generally do
dist-upgrades now by first upgrading apt and aptitude, then upgrading
the rest of the system, because each Debian release's aptitude package
has a much better dependency resolver than the previous one.

I generally use aptitude more than apt-get now, although there are still
differences between the two that are useful when one or the other cannot
resolve dependencies in specific situations.

Aptitude's interactive dependency resolver and apt preferences do a
fairly good job at implementing all three proposals, including downgrades.
Although I haven't attempted a full dist-downgrade in years, I have done
downgrades of families of hundreds of packagse (e.g. dependents of perl
and libglib) from Lenny to Etch with aptitude, apt preferences, and a
bit of manual hinting in the dependency resolver.