Решил попробовать prelink на своей толстой программе:
$ sudo prelink prog
/usr/sbin/prelink.bin: ..../prog: Cannot prelink against non-PIC shared library /usr/local/lib/libmy.so.0
Либа libmy.so точно скомпилена с -fPIC. Может prelink попортил её?