Gevent requires libevent 1.4, while Debian 5.0 Lenny only includes libevent 1.3.
Install libevent 1.4 from lenny-backports. First install backports:
# echo deb http://backports.debian.org/debian-backports squeeze-backports main \ > /etc/apt/sources.d/lenny-backports # aptitude update
Note that we're installing lenny-backports for Lenny, not squeeze-backports as the current backports instructions show.
Now install libevent-dev, specifying the lenny-backports release:
# aptitude -t lenny-backports libevent-dev
You should now be able to install gevent via easy_install as usual.