I've had this trouble and I think you need some of the font packages. Don't quote me on this but after installing some stuff it fixed itself.
If the problem is only in terminal windows, you could use a different terminal program like mrxvt which uses artwiz fonts and won't have the problem.