Comment 12 for bug 1247026

I was facing the same or a very similar problem: valgrind was complaining about a missing strlen in glibc despite having debug symbols installed (splitdebug in Gentoo).
The solution/work around I found was due to Christian Kruse [1]. It seems that during glibc compilation, strlen gets remove/rewritten due to code optimization and thus no longer exists as valgrind expects. The work around is to disable any change on strlen.
For documentation in case Christian's blog entry becomes unavailable, I am citing from his posting:

"I already was familiar with this problem and I knew using FEATURES="nostrip" and a re-emerge of sys-libs/glibc should help. But after doing that the problem was not gone. After some research I found out that with -O2 the GCC inlines strlen(). It is a code optimization, but in this case it causes valgrind to stop working. The solution is somewhat messy: you have to create a portage overlay of sys-libs/glibc and patch files/eblits/common.eblit: find the line containing append-flags -O2 -fno-strict-aliasing and append -fno-builtin-strlen. Then re-emerge glibc (do not forget to run ebuild glibc-ver.ebuild digest) and everything should work." (cited from [1]).

I can confirm that after a recompile of glibc, valgrind works again.

[1] http://ck.kennt-wayne.de/2012/jan/valgrind-again%3A-strlen-redirection