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.