The Prelink HOWTO is missing a hint that one should have emerged elfutils on x86 boxes before prelink can be emerged. I set up prelink on a ppc before without a problem and therefore didn't think of that.
Which version did you try? All current versions DEPEND on elfutils. If your error report is correct, it is no problem of the docs team but of elfutils since every package should DEPEND on what it needs.
Sorry but I'm quite new to this... I hope we're in the right category now.
Is there still a problem, prelink does depend on elfutils so I cannot see where the problem comes from ... Closing as I don't think this bug is real .. reopen if I'm wrong