It looks like there was briefly a version mismatch between python-service-identity and python-characteristic. I can no longer reproduce this. Can anyone else who was experiencing the problem confirm that it is resolved now?
A versionized depends might be nice here. Thanks, -- Andrew Starr-Bochicchio Ubuntu Developer <https://launchpad.net/~andrewsomething> Debian Developer <http://qa.debian.org/developer.php?login=asb> PGP/GPG Key ID: D53FDCB1