Solaris 8 2/04 with GCC 3.4.0 (SMCgcc build) and libiconv-1.9.2 (http://www.gnu.org/software/libiconv/) both installed in /usr/local. Ones gets (also on 3.0.5pre1) configure: WARNING: Sufficient support for iconv function was not found. regardless whether --with-libiconv=/usr/local is specified or not. LD_LIBRARY_PATH=/usr/local/lib has to be in the configure environment for the iconv detection to succeed. Having just CPPFLAGS=-I/usr/local/include LDFLAGS=-L/usr/local/lib is not enough. I am placing it as an installation problem, but it might be just as well only a documentation one.
you can use the crle tool to encode library search paths or you can use the -R<path> to the linker to encode the search path in the resulting binary.