Shameless self-promotion ... over the past year, I've been working on a project that aims to solve this dependency hell problem: http://www.stanford.edu/~pgbovine/cde.html
All you need to do is find a distro where jdee works, package it up with CDE, and then transport it to your own machine. email me if you have questions.
Does seem like quite a drastic solution to this problem though.
So you are using ptrace to intercept system calls and then copying files that are used. I suppose the problem with this is that when you are running CDE to generate the dependency list it is down to what is actually used, so if you don't hit every piece of code in the program when doing the "generation" part you may not get a completely working package.
I suppose you can do some evaluation on the binary to figure out which calls it might make during execution but this wouldn't work to well if the software in question is built using something dynamic like python where library calls may not necessarily be the same so cannot be predicted in advance?