After a clean installation I ran the cruft removal tool (from System->Administration) and a whole load of packages were ticked - I applied this and after 20 minutes saw that the majority of my installed desktop packages were removed. This cleaned up more than left over cruft(!).
ISO test image:
SUMMARY FOR SRU: A subset of users can render their systems unusable, by accidentally removing some packages needed for the system to work or, in some cases, all or most packages. This has been handled by checking that two essential packages (dash and gzip) are available in the Packages files, according to apt, and aborting if not. The regression risk for this change is that users might not be able to use the tool at all if the new test is too aggressive, but since update-manager uses the same heuristic, it should work very well.
PATCH: http://bazaar.launchpad.net/~systemcleaner-hackers/systemcleaner/intrepid-sru-1-proposal/changes (revision 108).
TEST CASE: Install without network access ("kvm -net none" suffices). After installation, install system-cleaner, and verify that "sudo system-cleaner find" finds a lot of cruft (at least several tens and possibly hundreds of packages). Install fixed system-cleaner (enabling networking is fine, as long as nothing runs "apt-get update"), and verify that "sudo system-cleaner find" returns nothing.