This is a brainfart by Redhat. First of all, the Annotate feature relies on the package "ghostscript-fonts" to be installed. Secondly, after installing that package the fonts live in a completely different directory.
Fix the problem by creating a symbolic link like this:
"ln -s /usr/share/fonts/default/Type1 /usr/share/ghostscript/fonts"
Finally, make sure that you are in fact referring to a font known to Image::Magick. You can get a list of supported fonts using the following Perl script:
#!/usr/bin/perl
use Image::Magick;
my $image = Image::Magick->new();
my @fonts = $image->QueryFont();
foreach $font (@fonts) { print $font . "\n"; }