After looking up for hours, it seems that time.h for some apparent reason has been used in ffmpeg 1.2.1 (this is what I tested). This caused conflict with the OS's own file of the same name. This causes the installation to break in CentOS 6.x, RHEL 5.6 and RHEL 6.x
While I cannot code in PHP (and can barely read PHP code), I have found a git repo maintained by tony2001 who has made changes to the original project and using his repo has helped me install it successfully on CentOS-6.2, CentOS-6.3 and CentOS-6.4.
You can find the repo here. This seems to solve the issues in CentOS 6.x, RHEL 5.6 and RHEL 6.x.
Hope this helps anyone else trying this in the future (and maybe someone else who lands up here eventually)
PS: Incidentally, at the time of writing this answer ffmpeg 2.0 has been released but I haven't got a chance to test it yet