What happens when you run the following by hand:
/usr/sbin/prelink -av -f (May take a while)
Sorry, that should be:
/usr/sbin/prelink -av -mR -f
and then
/usr/sbin/prelink -av -mR -q
The reason im having you try both.. is -f is a 'full' and -q is a 'quick'.. depending on how long its been since you ran a 'full', the script may be trying to do a full or a quick.. so for testing, i wanted to see that both would run.