It would be nice if valgrind's thread library supported the debugger interface so that when gdb is attached, you can get backtraces on all the client threads. What would also be useful is a way to break into gdb at any arbitrary time, to examine the client state. I added a User Request for this in my copy of valgrind 2.0.0 but the only way I could think of triggering it was via a signal handler. When gdb attaches, the only stack I can see is that of the signal handler's, which isn't very interesting. I suppose you could accomplish this by preloading a custom libthread_db on the gdb invocation, haven't looked into it in great detail.
gdbserver in Valgrind 3.7.0 provides the needed functionality