Это потому что вы ее красите в растре.
Варианта два:
1. Скачать по ссылке иконку в векторе (EPS-файл) и спокойно поменять цвета в Иллюстраторе (или другом векторном редакторе). Кликаете белой стрелкой (гор. клав.: A) на объекте и задаете цвет.
2. В Фотошопе (или ином растровом редакторе):
а) руками подчистить рваные края;
б) поверх иконки нарисовать объекты заново и окрасить в нужные цвета (инструментами Lasso, Pen Tool, либо просто создавая прямоугольники и трансформируя их);
в) обвести каждую деталь и залить нужным цветом (например Magic Wand или Lasso Tool).
Конечно же, первый вариант самый удобный, но можно и вторым способом. Чтобы уменьшить возможные огрехи все равно скачайте векторный файл и откройте в Фотошопе покрупнее, перекрасьте и уже через Save for Web сохраните в нужном размере PNG — рваных краев быть не должно.