"Times New Roman" typeface does not have any Japanese glyphs, as has already been stated in the comments. Therefore, depending on the Windows System, Excel will use glyphs from the supplemental fonts "Yu Gothic," "Meiryo," or "Arial Unicode MS." Therefore, even though Excel's GUI may list "Times New Roman" as a font, its glyphs cannot be from that font.
First of all the system which shall create a PDF from the Excel file must have a font containing appropriate Japanese glyphs. The system is in your case the CentOS Linux Distribution. So at first do # yum groupinstall "Japanese Support" as described in How to Install Asian Fonts on Red Hat & CentOS Linux Distributions.