The packages I'm toying with here are rather unknown, but nevertheless the problem is rather generic. Basically, I'm trying to compile Python module (called rql) with C++ extension. The extension uses external framework called gecode, which contains several libraries. I compiled gecode and installed locally. Now, let the output speak for itself:
red@devel:~/build/rql-0.23.3$ echo $LD_LIBRARY_PATH
/home/red/usr/lib
red@devel:~/build/rql-0.23.3$ ls $LD_LIBRARY_PATH | grep libgecodeint
libgecodeint.so
libgecodeint.so.22
libgecodeint.so.22.0
red@devel:~/build/rql-0.23.3$ python setup.py build
running build
running build.py
package init file './test/__init__.py' not found (or not a regular file)
running build_ext
building 'rql_solve' extension
g++ -pthread -shared build/temp.linux-i686-2.5/gecode-solver.o -lgecodeint -lgecodekernel -lgecodesearch -o build/lib.linux-i686-2.5/rql_solve.so
/usr/bin/ld: cannot find -lgecodeint
collect2: ld returned 1 exit status
error: command 'g++' failed with exit status 1