Comment 14 for bug 575333

Assuming that this error message is just a cosmetic issue and not a real problem (at least so far I didn't encounter any further side effects related to the udevd-work.. message), I found some workaround, which at least is hiding the error message.
Just add Plymouth to initramfs as described here http://www.ubuntugeek.com/quick-tipplymouth-themes-in-ubuntu-10-04-lucid-lynx.htm
This way Plymouth will come up much earlier in the boot process and the error message will be hidden beneath the nice Plymouth boot screen.