Primeiro, você precisa identificar o espaço de cores de suas imagens assim:
$ identify -verbose pieces-[0-3].png | grep Colorspace
A saída seria algo como:
Colorspace: Gray
Colorspace: Gray
Colorspace: sRGB
Colorspace: sRGB
No seu caso, as duas primeiras imagens estão usando o espaço de cores "cinza" e, em seguida, o Imagemagick define como um espaço de cores padrão na conversão final.
Finalmente, se você deseja usar cores na sua conversão, use o espaço de cores das duas últimas imagens, comando final:
$ convert pieces-[0-3].png -colorspace sRGB -append pieces-all.png