’ve adapted the instructions from this Ubuntu thread for Debian Lenny.
The original idea was to build ffmpeg with AAC support, but then I’ve found some other problems with mp3 codec, so I needed to apply a patch and rebuild everything.
So, I’m writing all the procedures in this post in a few steps, hoping that I’m not forgetting anything. I know that some steps could be avoided (e.g. building ffmpeg twice), but I’ll just transcribe everything the way that worked for me (as I remember).

First try

1. First edit your aptitude sources list

alfersoft:~# nano /etc/apt/sources.list

2. Add the following repositories
deb http://www.debian-multimedia.org stable main
deb http://www.backports.org/debian lenny-backports main contrib non-free

3. Update
sudo apt-get update

4. Remove current ffmpeg (if installed)
sudo apt-get remove ffmpeg x264 libx264-dev

5. Install necessary packages for the build. Note that I’ve removed libvpx-dev from the original Ubuntu thread.
sudo apt-get install build-essential subversion git-core checkinstall yasm texi2html \
    libfaac-dev libmp3lame-dev libopencore-amrnb-dev libopencore-amrwb-dev libsdl1.2-dev \
    libtheora-dev libvorbis-dev libx11-dev libxfixes-dev libxvidcore-dev \
    zlib1g-dev

6. Build and install x264.
cd
git clone git://git.videolan.org/x264.git
cd x264
./configure
make
sudo checkinstall --pkgname=x264 --pkgversion "2:0.`grep X264_BUILD x264.h -m1 | \
    cut -d' ' -f3`.`git rev-list HEAD | wc -l`+git`git rev-list HEAD -n 1 | \
    head -c 7`" --backup=no --deldoc=yes --fstrans=no --default

7. Build and install ffmpeg. Note that I’ve removed the option –enable-libtheora and –enable-libvpx from the original Ubuntu thread.
cd
svn checkout svn://svn.ffmpeg.org/ffmpeg/trunk ffmpeg
cd ffmpeg
./configure --enable-gpl --enable-version3 --enable-nonfree --enable-postproc \
    --enable-libfaac --enable-libmp3lame --enable-libopencore-amrnb \
    --enable-libopencore-amrwb --enable-libvorbis \
    --enable-libx264 --enable-libxvid --enable-x11grab
make
sudo checkinstall --pkgname=ffmpeg --pkgversion "4:SVN-r`LANG=C svn info | \
    grep Revision | awk '{ print $NF }'`" --backup=no --deldoc=yes --fstrans=no \
    --default
hash x264 ffmpeg ffplay