It certainly works for me, so I need your help to find out what's
going on.
Please download and install prelink-debuginfo-0.3.1-1 (or upgrade
both to 0.3.1-2), look into /var/log/prelink.log what options have
been passed to prelink (first line in the log) and run
gdb /usr/sbin/prelink
set args -av -mR -q # (or whatever options you see there)
run
and if that segfaults, I'd be interested in seeing backtrace (bt),
and later other details too.

I want to check if the problem disappeared after yesterday's massive 
update.  Where would I look?  /var/log/prelink.log shows nothing 
interesting.. 

If it segfaulted, root will get mail that the cron job failed.

Same problem here. FC2T3 all updated , with prelink and
prelink-debuginfo. Result from gdb:
parameters: /usr/sbin/prelink -av -mR -f

prelink: cxx.c:68: find_cxx_sym: Assertive `n < ndeps' failed.

Program received signal SIGABRT, Aborted.
0x080ad391 in kill ()

(gdb) bt
#0  0x080ad391 in kill ()
#1  0x080ad128 in raise ()
#2  0x00000006 in ?? ()
#3  0xfeeefa08 in ?? ()
#4  0x0808db1a in abort ()
Previous frame inner to this frame (corrupt stack?)
(gdb) 

Anything else I can provide to help?

Confirm same problem. FC2T3 updated, prelink and prelink-debuginfo =
0.3.1-2.
selinux=0 on boot (if it matters)
parameters: /usr/sbin/prelink -av -mR -q
but get same result without the -m and -q (although it seems to
prelink more libs before abort)

gdb:
[snip]
Prelinking /usr/bin/ksmserver
Detaching after fork from child process 17505.
prelink: cxx.c:68: find_cxx_sym: Assertion `n < ndeps' failed.

Program received signal SIGABRT, Aborted.
0x080ad391 in kill ()
(gdb) bt
#0  0x080ad391 in kill ()
#1  0x080ad128 in raise ()
#2  0x00000006 in ?? ()
#3  0xfef46428 in ?? ()
#4  0x0808db1a in abort ()
Previous frame inner to this frame (corrupt stack?)
(gdb)

Can I ask you for tarball created by:
tar cjhf /tmp/ksmserver.tar.bz2 `LD_TRACE_PRELINKING=1 LD_WARN= /usr/bin/ksmserver | awk '{print $3}'`
(or replace /usr/bin/ksmserver by whatever program you get this on)?
Also, please add -vvvv to prelink opts and see the messages printed before
the abort ().  Thanks.

Created attachment 99880 [details]
complete log of screen session when running prelink in gdb with args -aR -vvvv

Attached file uncompresses to 13MB textfile.

The ksmserver.tar.bz2 created from command in comment #6, is too large
to attach (7MB). Uploaded here:
http://www.pki.uib.no/images/ksmserver.tar.bz2

Do you want similar ones for other programs that fails?

Unfortunately, I cannot reproduce this.
ksmserver is prelinked just fine with:
prelink -vmR -c ./prelink.conf --ld-library-path . --dynamic-linker ././/ld-linux.so.2 ./ksmserver
(modified ksmserver, so that interpreter is ././/ld-linux.so.2).
So, can you please install prelink-debuginfo, run prelink under gdb
with the arguments you used and put a breakpoint:
b cxx.c:68 if n < ndeps
?
Then if that breakpoint gets hit, p info->dso->filename
p addr
p ndeps
p n
Then print info->dso[N] for N 0 through ndeps - 1 and info->dso->base
and info->dso->end?
Thanks.

Created attachment 99885 [details]
screenlog of gdb session  (snipped of some error msg) args: -aR -v

If you try once more, does it die on info->dso->filename /usr/bin/kdcop
as well?  If yes, can you build a tarball with kdcop and its dependencies
instead of ksmserver?

Created attachment 99891 [details]
screenlog of gdb session reproducing fault at kdcop file

kdcop.tar.bz2 created from similar command as in comment #6 uploaded here:
http://www.pki.uib.no/images/kdcop.tar.bz2

Can you please try
ftp://people.redhat.com/jakub/prelink/prelink*0.3.1-2.0.2*.rpm
?
It solves the prelink: cxx.c:68: find_cxx_sym: Assertive `n < ndeps' failed.
problem for Ingo Molnar who saw this problem on his box as well.
Thanks.

Confirms that prelink from comment #14 fixes problem for me.

I was just about to post that adding -q to the command and running
many times (20+) makes it able to finish the prelinking. 

Prelink from comment #14 completes run with args: -amvRf without
"ndeps" errors or aborts.

An errata has been issued which should help the problem 
described in this bug report. This report is therefore being 
closed with a resolution of ERRATA. For more information
on the solution and/or where to find the updated files, 
please follow the link below. You may reopen this bug report 
if the solution does not work for you.

http://rhn.redhat.com/errata/RHBA-2004-386.html