Instructions to compile:
kdenlive, melt, faad, faac, x264, theora, ffmpeg on Ubuntu Karmic

Very useful but insufficient instructions can be found at:
http://www.kdenlive.org/user-manual/downloading-and-installing-kdenlive/installing-source/installing-mlt-rendering-engine
See also:
HOWTO: Install and use the latest FFmpeg and x264
http://ubuntuforums.org/showthread.php?t=786095

Warning: The instructions below will break your mplayer/mencoder installed from Ubuntu Karmic packages.

Here's what Ubuntu Karmic users need to do:
These instructions are valid on Nov.26, 2009. There might be some changes in the future as bugs get removed/added from some of the libraries and related programs...

Installed packages:

apt-get install build-essential
apt-get install subversion git git-core
apt-get install yasm
apt-get install ubuntu-dev-tools
apt-get install libdirac-dev
apt-get install libschroedinger-dev
apt-get install libgsm1-dev
apt-get install libmp3lame-dev
apt-get install libopencore-amrnb-dev
apt-get install libopencore-amrwb-dev
apt-get install libvorbis-dev
apt-get install libgpac-dev
apt-get install libxvidcore4-dev
apt-get install libdc1394-22-dev
apt-get install libxml2-dev libsdl-dev
apt-get install libsdl-image1.2-dev
apt-get install libsox-dev libjack-dev ladspa-sdk
apt-get install libgtk2.0-dev
apt-get install libquicktime-dev
apt-get install frei0r-plugins-dev
apt-get install libsamplerate0-dev
apt-get install libqt4-dev
apt-get install kdelibs5-dev
apt-get install gtk-recordmydesktop recordmydesktop
apt-get install dvgrab
apt-get install dvdauthor

Important
Do not install ubuntu packages kdenlive, ffmpeg, libfaad, libfaac, libx264, libtheora. Make sure you have removed these packages. If "apt-get remove" will cause too many dependency removals on your system, then use "dpkg -r"
Make sure there are no libfaad, libfaac, libx264, libtheora left in:
/usr/lib
/usr/local/lib
There should neither be any .h include files related to the above libraries in:
/usr/include
/usr/local/include
Delete /usr/lib/i686 or /usr/local/lib/i686 if you find them, especially if they contain cmov/libav... libpostproc... libswscale...

faad
Download from http://www.audiocoding.com/downloads.html
Decompress
make clean (if previously compiled)
autoconf
./configure --prefix=/usr
make
sudo make install

faac
http://www.audiocoding.com/downloads.html
Decompress
make clean (if previously compiled)
edit common/mp4v2/mpeg4ip.h
comment out line 126 (valid Nov.26, 2009, might change soon):
// char *strcasestr(const char *haystack, const char *needle);

autoconf
./configure --prefix=/usr
make
sudo make install

x264
http://www.videolan.org/developers/x264.html
Decompress
make clean
./configure --prefix=/usr --enable-mp4-output --enable-shared
make
sudo make install

theora
http://theora.org/downloads/
Used: libtheora-1.1.1
Decompress
make clean
./configure --prefix=/usr
make
sudo make install

ffmpeg
Downloaded on Nov. 26, 2009. Two days earlier libtheora support was broken. So getting the latest possible version can be very important.
svn checkout svn://svn.ffmpeg.org/ffmpeg/trunk ffmpeg
make clean; make distclean
./configure --prefix=/usr --enable-shared --enable-libmp3lame --enable-gpl --enable-libfaad --enable-libvorbis --enable-pthreads --enable-libfaac --enable-libxvid --enable-postproc --enable-x11grab --enable-libgsm --enable-libx264 --enable-libtheora --enable-libdc1394 --enable-nonfree --disable-stripping --enable-avfilter --enable-libdirac --disable-decoder=libdirac --enable-libschroedinger --disable-encoder=libschroedinger --enable-avfilter-lavf --enable-libopencore-amrnb --enable-libopencore-amrwb --enable-version3 --enable-libtheora

make
sudo make install

MLT (generates "melt" executable)
git clone git://mltframework.org/mlt.git
make clean
./configure --prefix=/usr --enable-gpl --qimage-libdir=/usr/lib/ --qimage-includedir=/usr/include/qt4 --avformat-swscale --enable-mmx
make
make install

kdenlive
svn co https://kdenlive.svn.sourceforge.net/svnroot/kdenlive/trunk/kdenlive
cd kdenlive
mkdir build;cd build
(If it's a recompile: make clean)
cmake .. -DCMAKE_INSTALL_PREFIX=/usr
make
sudo make install
kdenlive
Very important: run the configuration wizard after every new compilation:
menu: Settings -> Run Config Wizard
Checking MLT engine, Tab:Installed modules: all should be with check mark
Next, Next, Next... till 4th dialog
Checking system: all should be with check mark
Finish
Then, in Kdenlive's main window, click on Render button (red dot with grey circle)
Verify that all formats are available:
Click on MPEG-4: all items in right column should be written against white background. If pink background then we have a problem! You will then have to recompile one of the encoding libraries, then recompile and re-install ffmpeg, then re-run kdenlive's configuration wizard.
Also click on H.264 and Theora to check for white background.

mplayer
svn checkout svn://svn.mplayerhq.hu/mplayer/trunk mplayer
./configure --prefix=/usr --codecsdir=/usr/lib/codecs --enable-gui
make
sudo make install
gmplayer, right click in window to open menu --> Preferences, tab: Audio. Check box on 3rd line: "Enable Software Mixer". OK. Quit.

Final tweaks
There might be some problems playing some formats with VLC and totem. I'm still investigating. To fix VLC I did:
sudo ln -s /usr/lib/libavutil.so /usr/lib/libavutil.so.49


I hope it works for you!

Thanks!!
I'm on a 9.10 64bit. Will the above automatically compile everything 64bit?

how's the sound on playback? is it choppy/noisy like in the official packaged version?

How to solve this error on mlt compile?

make[1]: Leaving directory `/home/al/devel/mlt/src/melt'
filter_sox.c:40:44: error: missing binary operator before token "("
filter_sox.c:46:44: error: missing binary operator before token "("
filter_sox.c:82:43: error: missing binary operator before token "("
filter_sox.c:108:43: error: missing binary operator before token "("
filter_sox.c:138:43: error: missing binary operator before token "("
filter_sox.c:184:43: error: missing binary operator before token "("
filter_sox.c:214:43: error: missing binary operator before token "("
make[2]: *** [depend] Error 1
make[1]: *** [depend] Error 1
make: *** [all] Error 1

Could it be a gcc version-related problem?
I used gcc (Ubuntu 4.4.1-4ubuntu8) 4.4.1

vpxavier asks:
> I see that the two following modules are not installed:
> AVformat Module (FFmpeg)
> DV module (libdv)

Here's what I get for ldd /usr/bin/ffmpeg
linux-gate.so.1 => (0x00fc9000)
libavfilter.so.1 => /usr/lib/libavfilter.so.1 (0x0027e000)
libpostproc.so.51 => /usr/local/lib/libpostproc.so.51 (0x0028a000)
libavdevice.so.52 => /usr/lib/libavdevice.so.52 (0x008b1000)
libavformat.so.52 => /usr/lib/libavformat.so.52 (0x00aa3000)
libavcodec.so.52 => /usr/lib/libavcodec.so.52 (0x00fca000)
libavutil.so.50 => /usr/lib/libavutil.so.50 (0x00eed000)
libswscale.so.0 => /usr/lib/i686/cmov/libswscale.so.0 (0x00e25000)
libm.so.6 => /lib/tls/i686/cmov/libm.so.6 (0x00a5a000)
libpthread.so.0 => /lib/tls/i686/cmov/libpthread.so.0 (0x00be0000)
libc.so.6 => /lib/tls/i686/cmov/libc.so.6 (0x0066f000)
libdc1394.so.22 => /usr/lib/libdc1394.so.22 (0x00110000)
libasound.so.2 => /usr/lib/libasound.so.2 (0x00183000)
libjack.so.0 => /usr/local/lib/libjack.so.0 (0x0024a000)
libX11.so.6 => /usr/lib/libX11.so.6 (0x00298000)
libXext.so.6 => /usr/lib/libXext.so.6 (0x00264000)
libz.so.1 => /lib/libz.so.1 (0x0084e000)
libbz2.so.1.0 => /lib/libbz2.so.1.0 (0x00912000)
libdirac_encoder.so.0 => /usr/lib/libdirac_encoder.so.0 (0x003c7000)
libfaac.so.0 => /usr/lib/libfaac.so.0 (0x0045b000)
libgsm.so.1 => /usr/lib/libgsm.so.1 (0x0046d000)
libmp3lame.so.0 => /usr/lib/libmp3lame.so.0 (0x0047b000)
libopencore-amrnb.so.0 => /usr/lib/libopencore-amrnb.so.0 (0x004ee000)
libopencore-amrwb.so.0 => /usr/lib/libopencore-amrwb.so.0 (0x00606000)
libschroedinger-1.0.so.0 => /usr/lib/libschroedinger-1.0.so.0 (0x00521000)
libtheoraenc.so.1 => /usr/lib/libtheoraenc.so.1 (0x005a2000)
libtheoradec.so.1 => /usr/lib/libtheoradec.so.1 (0x005e7000)
libvorbisenc.so.2 => /usr/lib/libvorbisenc.so.2 (0x00924000)
libvorbis.so.0 => /usr/lib/libvorbis.so.0 (0x00620000)
libx264.so.79 => /usr/lib/libx264.so.79 (0x00bf9000)
libxvidcore.so.4 => /usr/lib/libxvidcore.so.4 (0x00cd2000)
libdl.so.2 => /lib/tls/i686/cmov/libdl.so.2 (0x008d5000)
libavutil.so.49 => /usr/lib/libavutil.so.49 (0x00649000)
/lib/ld-linux.so.2 (0x008f4000)
libraw1394.so.11 => /usr/lib/libraw1394.so.11 (0x00f76000)
librt.so.1 => /lib/tls/i686/cmov/librt.so.1 (0x00274000)
libsamplerate.so.0 => /usr/lib/libsamplerate.so.0 (0x01bfc000)
libcelt.so.0 => /usr/local/lib/libcelt.so.0 (0x0065a000)
libxcb.so.1 => /usr/lib/libxcb.so.1 (0x007b3000)
libXau.so.6 => /usr/lib/libXau.so.6 (0x00286000)
libstdc++.so.6 => /usr/lib/libstdc++.so.6 (0x04464000)
libgcc_s.so.1 => /lib/libgcc_s.so.1 (0x007d1000)
liboil-0.3.so.0 => /usr/lib/liboil-0.3.so.0 (0x00b65000)
libogg.so.0 => /usr/lib/libogg.so.0 (0x007ef000)
libXdmcp.so.6 => /usr/lib/libXdmcp.so.6 (0x00f61000)

What do your libav... links look like?