libmpeg3.c:494: libmpeg3.h: No such file or directory" This looks ambiguous to me. is it libmpeg3.h that's missing?

Yes! Line 494 of libmpeg3.c is #include "libmpeg3.h" and the error message is telling you that the compiler cannot find the file.

As you are certain that the file does exist on your system, this suggests that your include path does not have the correct directories set up.

I'm not familiar with gcc or linux, but looking at the output you referenced, the only include path specified is -I/usr/lib/perl5/5.6.1/i586-linux/CORE so as a 'quick fix' you could try copying libmpeg3.h into that dir and see how you get on.

There is almost certainly a better way of doing this. Eg. Adding /usr/include/libmpeg3 to the appropriate environment var (include?), but I'm unsure of that.