ldd can't find library in LD_LIBRARY_PATH
The binaries I had were looking for the 32-bit versions of the shared libraries, I had the 64-bit installed. Stupid mistake. LDD didn't produce a very insightful error message, but the binary did when I tried to run it.
Did you export LD_LIBRARY_PATH? the export keyword tells Bash to send any variables to subprocesses - otherwise ldd will never see LD_LIBRARY_PATH.