It would save everyone a lot of time if the patches provided by the Debian Perl Group were applied. Particularly the one by gregor herrmann rt.cpan.org/Ticket/Attachment/1044954...
After comparing against File::MMagic, File::MMagic::XS, File::Type, I ended up choosing File::LibMagic because it has the least problems and looks like being the most maintained (although it would be nice if the author cleans up the RT queue).
For those stuck without a C compiler, File::Type or File::Magic can be an alternative.
1 hidden unhelpful review