No Ubuntu, os cabeçalhos FFmpeg são distribuídos entre vários pacotes, que são criados a partir do pacote ffmpeg
source. Eu acho que você deve instalar todos eles ( lista aqui ):
$ sudo apt-get install libavcodec-dev libavcodec-ffmpeg-dev libavdevice-dev libavdevice-ffmpeg-dev \
libavfilter-dev libavfilter-ffmpeg-dev libavformat-dev libavformat-ffmpeg-dev libavresample-dev \
libavresample-ffmpeg-dev libavutil-dev libavutil-ffmpeg-dev libpostproc-dev libpostproc-ffmpeg-dev \
libswresample-dev libswresample-ffmpeg-dev libswscale-dev libswscale-ffmpeg-dev