If you are developing a map legend then chances are that you want the legend to be relatively small and also have the ability to look ok with a transparent background - in which case try using something like Verdana at 8pt with no anti-aliasing.
You should find that this looks good and, because there is no anti-aliasing, transparency works fine with it.
(In general though, I agree with everything mThomas said)
Thinking about it if you are 'add[ing] text into an image' then what mThomas said about 16 million colours is probably your problem; up the colour depth to 16 million, add your text, then reduce it back to 256, or whatever, after.
=)
PetitPal.