While upgrading from Ubuntu 9.10 to 10.04, faced "The package 'ubuntu-desktop' is marked for removal but it is in the removal blacklist.".
Turns out this was because I had both ubuntu-desktop and xubuntu-desktop.
Solution: Removed xubuntu-desktop with
sudo apt-get remove xubuntu-desktop
Upgrade continued without any problem after that.