ld finds some libraries, but not others.

[Jonathan Ryshpan]

A build is failing with the error cannot find <library> for libraries
that are, in fact present on the system.

I made a very simple test bed, consisting of the empty file conftest.c,
which I attempt to compile and link with various libraries.  All the
libraries are in /usr/lib64.  Sometimes the compilation fails with
        undefined reference to `main'
which is what I would expect, but often it fails with
        cannot find -l<whatever>
I have no idea what's happening.  Can anyone explain?

Here's an example of what's going on.  This is a listing of some files
in /usr/lib64:
        1167 lib64 $ ll libICE.so* libgd.so* libkate.so* libkblog.so.*
        lrwxrwxrwx. 1 root root     15 Nov  9 18:28 libICE.so -> libICE.so.6.3.0*
        lrwxrwxrwx. 1 root root     15 Nov  9 08:02 libICE.so.6 -> libICE.so.6.3.0*
        -rwxr-xr-x. 1 root root  98328 Jun 21 09:37 libICE.so.6.3.0*
        lrwxrwxrwx. 1 root root     14 Nov  9 08:14 libgd.so.2 -> libgd.so.2.0.0*
        -rwxr-xr-x. 1 root root 278048 Oct 26 20:15 libgd.so.2.0.0*
        lrwxrwxrwx. 1 root root     16 Nov  9 08:06 libkate.so.1 -> libkate.so.1.2.1*
        -rwxr-xr-x. 1 root root  75640 Mar  7  2011 libkate.so.1.2.1*
        lrwxrwxrwx. 1 root root     17 Nov 13 09:03 libkblog.so.4 -> libkblog.so.4.7.0*
        -rwxr-xr-x. 1 root root 312960 Nov  4 10:05 libkblog.so.4.7.0*
And here's a attempt to compile the dummy linking to them:
        1033 wview-5.19.0 $ gcc -o conftest -g -O2 conftest.c -lICE
        /usr/lib/gcc/x86_64-redhat-linux/4.6.2/../../../../lib64/crt1.o: In function `_start':
        (.text+0x20): undefined reference to `main'
        collect2: ld returned 1 exit status
        1034 wview-5.19.0 $ gcc -o conftest -g -O2 conftest.c -lgd
        /usr/bin/ld: cannot find -lgd
        collect2: ld returned 1 exit status
        1035 wview-5.19.0 $ gcc -o conftest -g -O2 conftest.c -lkate
        /usr/bin/ld: cannot find -lkate
        collect2: ld returned 1 exit status
        1036 wview-5.19.0 $ gcc -o conftest -g -O2 conftest.c -lkblog
        /usr/lib/gcc/x86_64-redhat-linux/4.6.2/../../../../lib64/crt1.o: In function `_start':
        (.text+0x20): undefined reference to `main'
        collect2: ld returned 1 exit status