You have to install the "msttcorefonts" package in your system.
Just did that on my Debian here, worked a charm.
Well, I had to add "contrib" to the apt sources, but after that, all is well.

i have same problem, and i don't want install msttfcorefonts from special non-free repos or with special installers.

I think it must work by default, and i do these tests:
http://www.dagondesign.com/articles/checking-for-gd-support-on-your-server/
GD is supported by your server!
GD Version Yes
FreeType Support Yes
FreeType Linkage Yes
T1Lib Support Yes
GIF Read Support Yes
GIF Create Support Yes
JPG Support Yes
PNG Support Yes
WBMP Support Yes
XPM Support Yes
XBM Support Yes
JIS-mapped Japanese Font Support No

this test code i try also:

<?php
header ('Content-type: image/png');
$im = @imagecreatetruecolor(120, 20)
or die('Cannot Initialize new GD image stream');
$text_color = imagecolorallocate($im, 233, 14, 91);
imagestring($im, 1, 5, 5, 'A Simple Text String', $text_color);
imagepng($im);
imagedestroy($im);
?>

result is good: image with text presented like at http://www.php.net/manual/en/function.imagecreate.php example 1.

i test it on apache2 2.2.6 + php 5.2.2 + php5-gd2 + mantis 1.2.0, and nothing else.
config_inc.php don't have anything about graph.
in /library i have default ezc/ directoty, no jpgraph.
in web config ezc selected.

but i cannit see graph with "cannot find font" in mantis.
Maybe mantis require special fonts, not common sans/serif/like families of fonts? but why?

Same problem here with Mantis 1.2.1 and Mantis Graphs 1.0, using bundled library.

In my case the problem was PHP safe mode. Mantis, running under my UID, couldn't read the directories with the fonts, owned by root.

Disabling safe mode solved the problem for me.

i added to my mantis configfile.

$t_font_path = dirname(FILE).'/jpgraph/truetype/';
define('TTF_DIR',$t_font_path);

There seems to be a problem with central font management.
The ttf_dir constant seems to be initialised a bit scary ...