I've looked through these forums and I cannot find any way to make H.264 video and AAC audio available. I've tried recompiling FFmpeg from source, uninstalling and reinstalling kdenlive from the packages provided on this distro of Kubuntu, making sure to delete all configuration files, I've checked ffmpeg, and the options seem enabled:

FFmpeg version SVN-r23791, Copyright (c) 2000-2010 the FFmpeg developers
built on Jun 25 2010 21:19:10 with gcc 4.4.1
configuration: --enable-gpl --enable-version3 --enable-nonfree --enable-postproc --enable-pthreads --enable-libfaac --enable-libmp3lame --enable-libopencore-amrnb --enable-libopencore-amrwb --enable-libtheora --enable-libx264 --enable-libxvid --enable-x11grab
libavutil 50.19. 0 / 50.19. 0
libavcodec 52.78. 0 / 52.78. 0
libavformat 52.71. 0 / 52.71. 0
libavdevice 52. 2. 0 / 52. 2. 0
libavfilter 1.20. 0 / 1.20. 0
libswscale 0.11. 0 / 0.11. 0
libpostproc 51. 2. 0 / 51. 2. 0

The sections for H.264 and Xvid remain greyed out. Is there anything else I could try?

After you recompiled ffmpeg did you also recompile MLT?
This is necessary.