Comment 1 for bug 1047560

I tried this several times in a clean quantal amd64 chroot...

The following packages were automatically installed and are no longer required:
  ca-certificates libgcrypt11 libgpg-error0 libjs-jquery libjs-sphinxdoc libjs-underscore libxml2 libxslt1.1 libyaml-0-2
  openssl python-amqplib python-anyjson python-cliff python-cmd2 python-eventlet python-formencode python-gflags
  python-greenlet python-httplib2 python-iso8601 python-kombu python-lxml python-netaddr python-openid python-openssl
  python-paste python-pastedeploy python-pastescript python-pkg-resources python-prettytable python-pyparsing python-pyudev
  python-quantum python-quantumclient python-repoze.lru python-routes python-scgi python-setuptools python-simplejson
  python-sqlalchemy python-sqlalchemy-ext python-webob python-yaml quantum-common sgml-base xml-core
Use 'apt-get autoremove' to remove them.
The following packages will be REMOVED:
  quantum-server*
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
After this operation, 110 kB disk space will be freed.
Do you want to continue [Y/n]?
(Reading database ... 20282 files and directories currently installed.)
Removing quantum-server ...
Purging configuration files for quantum-server ..
#

Same basic result on precise as well.

Whats puzzling about your result is that update-rc.d is only run in the postinst, which isn't called during remove or purge.

Can you apport-collect on a box you see this on so I can look at the dependencies?