I'm starting to think this is caused by something else. I retraced your steps to the letter (with and without kernel modules loaded) and still no problems. Try removing the packages with --purge, maybe there is some old dirt left in there... It's a bit strange that your dmsetup softlink is dated Sept (you say it works when you delete it manually... but then how does it get recreated with a Sept date ?)

Also, check that you do not have a stuck /var/lib/dpkg/info/dmsetup.preinst , after install it should contain

#!/bin/sh
if [ -e /etc/udev/rules.d/65_dmsetup.rules ] ; then rm /etc/udev/rules.d/65_dmsetup.rules ; fi