For a bug in 2.16.92 and 2.16.93 versions of binutils, the –as-needed flag ended up doing something more than is documented, instead of simply skipping DT_NEEDED entries, it also discarded the search path for the libraries passed in command line that get discarded.
If from one side this can be seen as a correct behaviour, this broke with almost every build system, like for instance everything using libtool. It broke in the sense that it ended up looking up the libraries installed in the system rather than the ones just build, failing to find them if they weren’t installed and cross-linking them if they were. The result is not good.
Luckily there is a patch laying in binutils-devel mailing list and it has been committed hopefully for 2.17. In the mean time you have either to cope with the problem or simply use my overlay and use binutils that are there. They are already patched for -Bdirect and -hashvals support (the latter more to avoid breakages).
I might end up closing some bugs pointing to this blog post as it’s boring to repeat the same stuff too many times 😉