Oh, the joys of Debian/unstable: a few days ago, udev was being upgraded - and introduced a conflict with mdadm. Unfortunately, it did not set the usual Conflicts: tag, so one has to go to the changelog to find a pretty terse comment:

     * New upstream release.
     + vol_id and libvolume_id have been removed. (Closes: #500883, #534765)
       Breaks: dmsetup (<< 2.02.51-1), mdadm (<< 3.0-3)

The real story however is told in #541884:

The next udev upload will not contain the vol_id program anymore, since
it was removed by the upstream maintainer in May, and will declare a
Breaks relationship with the current version of your package.

You need to update the rules file in your package to use:
   /sbin/blkid -o udev -p ...
instead of:
  vol_id --export ...
Your package will need to depend on util-linux >> 2.16.

Well, I won't blame them for ripping things apart, that's what unstable is for. In fact, I'd wish they'd do this more often to get rid of old packages. ~~But a Conflicts: tag would have been nice too :-\~~

Update: the new udev package sets another tag called Breaks instead of Conflicts. Wow, I think I've never seen a Breaks: tag before.