Você pode usar
convert original.png -fuzz 15% -fill '#00ff00' -opaque '#ff0000' recolored.png
quanto maior for o fator fuzz, mais cores semelhantes serão correspondentes. (Observe a ordem dos parâmetros: fill
é a cor mas é a primeira). Consulte a página de base de substituição do ImageMagick.