$ udevadm monitor
KERNEL[1250930556.085871] add /kernel/uids/111 (uids)
UDEV [1250930556.087481] add /kernel/uids/111 (uids)
KERNEL[1250930556.099782] remove /kernel/uids/111 (uids)
UDEV [1250930556.099818] remove /kernel/uids/111 (uids)
I also found that the program that causes the CPU load is "hal-acl-tool" but not directly. In fact, hal-acl-tool wasn't consuming a lot of CPU and top wasn't showing anything. With process accounting I found that there are 1000s of invocations of /usr/lib/policykit/polkit-read-auth-helper:
$ lastcomm |grep polkit-read-aut | wc -l
61161
in a couple of minutes (!). This seems to be a bug that troubles other people too.
Finaly, I concluded that the problem is not related to uid-add events but to session creation. The problem is caused by console kit and its pam hook: pam_ck_connector.so. For newer debian versions (read: testing) you can disable this by running (as root) pam-auth-update and deselecting the "ConsoleKit Session Management".
WARNING: I'm not aware of the drawbacks of disabling "ConsoleKit Session Management", so do this at your own risk.