The Udev rule_generator.functions file has a "sysreadlink" function that uses the readlink binary. That functions file also sets PATH to /sbin:/bin (it was designed to be used before /usr is mounted), which means readlink needs to be in either /sbin or /bin.
Chapter 6 coreutils leaves it in /usr/bin (while moving many other programs). I think we should add readlink to the list of programs being moved to /bin.
As for other distros, at least Debian has it in /bin (I don't know about any others). See:
http://marc.theaimsgroup.com/?l=linux-hotplug-devel&m=116285351800962&w=2