You need to download ffmpeg and build from source if you haven't already done so. Uninstall your current ffmpeg installation or package before you begin.
First, you'll need to install the subversion client which lets you download source code if you don't already have it. Check your distribution for a subversion package you can install.
Then see http://ffmpeg.mplayerhq.hu/download.html for the download instructions to get the source code. As it says, you'll need to run:
svn checkout svn://svn.mplayerhq.hu/ffmpeg/trunk ffmpeg
This will get the source code for ffmeg.
cd to the ffmpeg directory, the run:
./configure --enable-mp3lame --enable-libogg --enable-vorbis --enable-shared
If you don't have lame, or ogg, or vorbis installed, remove any of those parameters. The main thing is that "--enable-shared" needs to be turned on.
What this does is build the ffmpeg libraries as shared files, which will make it
possible for ffmpeg-php to use these same libraries when you build it.
Then do make and make install to install ffmpeg (it will go into /usr/local/ directories).
After you've done this, go back to the ffmpeg-php source and try configure and make once again. Should work this time.