ANN: py2app 0.1
Even at this early stage, it's probably the most advanced python packaging utility out there with regard to dependency analysis. It's at a "works for me and the two other people that have tried it" stage. It's not particularly documented, and I don't have time to document it today, but you should be able to get along given the examples. Since it is very similar to py2exe in design, you can also borrow ideas from there.
If you have any issues with py2app, please let me know. Provide source if possible. I'm particularly interested in problematic packages which use import tricks or in-package data files such as PIL or pygame. These two are explicitly supported by the extensible "recipe" mechanism of py2app, but there are surely others. I believe PEAK, ZConfig, Twisted, etc. may do one or both of these things. Until a recipe is created for a particular problematic package, you may always just include it wholesale with the -p argument.
Download and related links are here: http://undefined.org/python/#py2app