Installing prelink-20060213 does leave a /etc/prelink.conf, so is usable. However, 20060712 doesn't. Unmerging 20060213 leaves the config file so is only an issue for people newly merging it. Couldn't see any obvious change in the ebuild between the versions?
Has nothing to do w/ KDE.
You can run env-update and it should generate prelink.conf automatically. prelink.conf used to be installed but it quickly was overwritten so a bug was filed, so it is now no longer installed. Best find a was for env-update to run after an emerge (but I think that was discouraged. )
Looks like WONTFIX.