I recently understood why easy_install wasn't able to find so many of our packages anymore.
The problem was due to a recent change on our website. The project page was ajaxified, and since easy_install uses some screenscrapping techniques to get distribution archives, it can not find the files it is looking for.
To fix this, we should make our tarballs downloadable from PyPI, by using
python setup.py register sdist upload
instead of the current:
python setup.py register
Uploading our public python software packages to PyPI will make them easy_installable in a breeze !