when running updatedb for the first time after emerging rlocate, it fails due to the non-existing /var/lib/rlocate directory. Maybe it would've been created by the rlocate-daemon after some changes were reported by the kernel module, but it wasn't by the ebuild nor by starting the service. Wouldn't have been created by the updatedb entry in cron.daily either. This should be done in the ebuild imho. (marked trivial for obvious reasons ;))
Current versions (as 0.5.5) create that directory. Close?
Fixed. Added "keepdir /var/lib/rlocate" to rlocate-0.5.5.