Preview can't find fonts used in eps file generated by gnuplot
Preview's postscript conversion doesn't use Times New Roman, but you (probably) can use Times Roman. I'm not familiar with Gnuplot, so I'm not sure how to set fonts, but the name is "Times-Roman"