Using the KDElive Build Script Classic 3.1 and having installed everything on the Wiki that I could find, I have checked out these revisions but I am failing to build:

eljefe@eljefe-desktop:~/kdenlive_Debian_080429$ ./kdenlive_install.sh info
FFmpeg SVN version:
Revision: 13021
Last Changed Date: 2008-04-29 13:32:06 -0500 (Tue, 29 Apr 2008)
MLT SVN version:
Revision: 1114
Last Changed Date: 2008-04-23 01:29:46 -0500 (Wed, 23 Apr 2008)
MLT++ SVN version:
Revision: 1114
Last Changed Date: 2008-04-23 01:32:01 -0500 (Wed, 23 Apr 2008)
Kdenlive SVN version:
Revision: 2168
Last Changed Date: 2008-04-25 12:24:27 -0500 (Fri, 25 Apr 2008)
eljefe@eljefe-desktop:~/kdenlive_Debian_080429$ 

Here is the last of my build, which fails:

...
...
...
make[2]: Leaving directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules/lumas'
make[2]: Entering directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules/xine'
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread -I../../ -DARCH_X86   -c -o factory.o factory.c
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread -I../../ -DARCH_X86   -c -o deinterlace.o deinterlace.c
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread -I../../ -DARCH_X86   -c -o cpu_accel.o cpu_accel.c
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread -I../../ -DARCH_X86   -c -o filter_deinterlace.o filter_deinterlace.c
cc -shared -o ../libmltxine.so factory.o deinterlace.o cpu_accel.o filter_deinterlace.o -L../../framework -lmlt
make[2]: Leaving directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules/xine'
make[2]: Entering directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules/normalize'
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread -I../..   -c -o factory.o factory.c
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread -I../..   -c -o filter_volume.o filter_volume.c
cc -shared -o ../libmltnormalize.so factory.o filter_volume.o  -L../../framework -lmlt
make[2]: Leaving directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules/normalize'
make[2]: Entering directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules/dv'
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread `pkg-config --cflags libdv` -I../..   -c -o factory.o factory.c
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread `pkg-config --cflags libdv` -I../..   -c -o producer_libdv.o producer_libdv.c
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread `pkg-config --cflags libdv` -I../..   -c -o consumer_libdv.o consumer_libdv.c
cc -shared -o ../libmltdv.so factory.o producer_libdv.o consumer_libdv.o `pkg-config --libs libdv` -L../../framework -lmlt
make[2]: Leaving directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules/dv'
make[2]: Entering directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules/avformat'
cc -Wall -fPIC -DPIC   -O4 -pipe -fomit-frame-pointer -ffast-math -DUSE_MMX -g -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -pthread -I/include   -I../.. -DSWSCALE   -c -o factory.o factory.c
factory.c:34:22: error: avformat.h: No such file or directory
factory.c: In function ‘avformat_init’:
factory.c:90: warning: implicit declaration of function ‘av_register_all’
factory.c:92: warning: implicit declaration of function ‘av_log_set_level’
make[2]: *** [factory.o] Error 1
make[2]: Leaving directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules/avformat'
make[1]: *** [all] Error 1
make[1]: Leaving directory `/home/eljefe/kdenlive_Debian_080429/mlt/src/modules'
make: *** [all] Error 1
eljefe@eljefe-desktop:~/kdenlive_Debian_080429$

Any suggestions out there?

It looks like it did not install ffmpeg correctly. Do you use latest version of installation script? I had this problem when i tried to compile kdenlive against system ffmpeg libraries, but script 3.1 did help to me.