I recently started supporting Number Drill, my math drill software, for Linux a few days ago. Number Drill is a pure python program with the external dependencies of pygame, rabbyt, PyOpenGL and a few others. All of which were in the Debian and Fedora repositories.
I originally tried using cx_Freeze to make a binary to distribute. But I kept on running into major problems with this method. And as it ended up I would have to include a plethora of .so files (such as all of pygame and everything that it depends on, libssl and everything it depends on etc) just to avoid version conflicts that resulted in segfaults. Not to mention the resulting package ending up far larger than it should be.
That was about the time Matthew suggested just distributing the pyc files (gasp! I know, it's not open source) and letting package systems like deb and rpm handle dependencies. This method has ended up working almost perfectly. Both Ubuntu 9.04 and Fedora 11 have all the dependencies I require available. The resulting packages are very small (no binaries included, just the python byte code).
The only disadvantage is that it requires the latest versions of Ubuntu or Fedora (as of today) as they are the only releases that have new enough versions of my dependencies.
We wrote a bash script that automatically packages up a pure python program into both a deb and rpm. If you are interested in here it is: http://arcticpaint.com/static/blog/python_to_deb_rpm.sh
I believe that this method of packaging is even more effective in the open source world. It essentially just makes getting your program to run from source as easy as possible.