I believe the reason is given at : http://sourceware.org/ml/binutils/2006-10/msg00186.html The way I also came across the problem was that prelink was failing. But in my case , the prelink check that was failing was one where it is confirmed that PLT REL entries are placed either immediately before or after normal REL entries . ps - why does gmail mess up the formatting of the posts ?