Eu acho que é porque fontes padrão são vetores, e esses gifs são imagens raster e estão sendo redimensionadas mal. A solução pode ser recriar os gifs como fontes com algo como fontforge .
Considerando que o cutepdf usa ghostscript (que é o mecanismo padrão de postscript da FOSS), duvido que seu cutepdf faça algo estranho.