parted-1.8.2-1.fc6 has just appeared and contains the symlink /usr/lib/libparted-1.8.so.2 rather than /usr/lib/libparted-1.8.so.0, the latter being what /usr/lib/libbdevid.so.5.1.19.0.2 from mkinitrd-5.1.19.0.2-1 links against. Thus mkinitrd needs to be rebuilt to match the new parted package.
Yup. I noticed this as it breaks anaconda completely.
Fixed in mkinitrd-5.1.19.0.3-1