Здравствуйте, Reactor.
Я посмотрел - все картинки на которые Вы дали ссылки являются 8 битными изображениями типа .bmp.
Я попробовал, посмотреть, могу ли я их сохранить на своей версии в качестве 8 бит.
Результат - да. Когда сохраняю в этом формате доступен только один режим - 8 бит.
Затем я попробовал открыть любое свое изображение и сохранить его в том же формате. В результате - та же ситуация, что и у Вас - только выше 8 бит.
Попробовал выйти из этой ситуации следующим образом - отойти от стандартного режима RGB, и в главном меню выбрал - Образ->Режим->Определ цвета.
Так по крайней мере в русификации, что у меня стоит. Если у Вас английская, то в главном меня - 3 пункт, в нем самый верхний, и в под меню 4.
Там выбираю - 256 цветов и нажимаю Ок.
Теперь можно легко сохранить в 8 битном bmp.
На счет файла, в котором нужно сделать прозрачный фон. Также как и раньше говорил в режиме выберете теперь - RGB.
А далее преобразуйте из фона в обычный щелкнув два раза на нем и в появившемся меню нажав ок. Далее создайте новый слой, который разместите под предыдущем.
На том слое где картинка воспользуйтесь волшебной палочкой (W). И удалите то что не надо. Сохраните в GIF, при этом поставьте флажок на меню Прозрачный фон.

Что касается замены цвета, то дело в том, что в файле довольно много переливаний цветов. Там вверху есть такие же цвета что и в самом окне. Поэтому если вы их "зацепите" в замене, то и в центре они поменяются. Единственное что я могу Вам посоветовать - изменять по частям. Хоть это и дольше будет. Но возможно выйдет с первого раза выделить с такой погрешностью что и сразу результат будет приемлем. Желаю Вам удачи.

Уважаемый Reactor.
В общем и целом согласен с коллегами, но позволю себе некоторые дополнения…
Что касаемо прозрачного фона в файле с индексированным цветом.
Собственно, первая часть Вашего вопроса несколько перекликается со второй. А именно: PhotoShop никогда не даст сохранить Вам исходник с битовой глубиной в то время, когда последний имеет полную палитру цветового охвата (RGB, 8 bit на канал). Всегда, преследуя выше описанную Вами цель, Вы должны предварительно перевести режим цветовой модели в ИНДЕКСИРОВАННЫЕ цвета, только после этого редактор пустит Вас в 8-битный BMP.

Советую Вам как можно реже пользоваться «Волшебной палочкой», особенно в тех случаях, когда речь идёт о «поползновениях» в адрес равномерной цветовой заливки, как то – фона в данном случае.
Для подобных целей в PhotoShop имеется гораздо «более умный» инструмент «Выделение по цветовому диапазону» (меню «Выделение» – «Цветовой диапазон»).
Использовать этот инструмент при определённых навыках не составляет особой сложности.

Применительно к Вашему случаю. Откройте исходник в редакторе. Переведите цветовую палитру в режим RGB, на панели инструментов возьмите «пипетку» и кликните нею по белому фону на исходнике. Пройдите далее «Выделение» – «Цветовой диапазон». Выставьте небольшой (опционально) разброс «чувствительности» инструмента, да бы не спровоцировать последний на посягательства на размытые белым области на исходнике. Подтвердите.
Посмотреть.
Белые пиксели будут выделенными на всём поле изображения. Инвертируйте выделение. На панели инструментов возьмите любой инструмент выделения (например – «Лассо»), поставьте курсор внутрь любого выделенного участка, нажмите правую мышь и из контекстного меню выберите «Скопировать на новый слой». В палитре слоёв удалите нижний слой. Вы получили изображение иконок на прозрачном фоне…
Посмотреть.
Теперь снова переведите палитру в индексированный цвет и сохраните Ваш вновь полученный исходник в 8-битный BMP, указав в параметрах индексации цвета следующие опции: Палитра – Локальная (селективная), Цвет – 256 (только в случае принудительного преобразования в WEB в соответствующем поле), галочка в опции «Прозрачность» обязательна, Подложка – Без цвета, Дизеринг – Диффузия, степень последней – опционально (не ниже 70%).

По второй части. Откройте исходник. Переведите палитру в режим RGB. В палитре слоёв создайте копию основного слоя. Возьмите «Полигональное лассо» с нулевой растушёвкой (выставляется на панели параметров под панелью меню). Увеличьте масштаб изображения (скролом, ежели таковая опция задействована в настройках программы, или сочетанием «Ctrl»+«+»). Грубо обведите «Лассо» белую область внутри рамки, слегка захватывая саму рамку.
Посмотреть.
Уменьшите масштаб до нормального. Возьмите пипетку и кликните нею по белому полю внутри рамки. Задействуйте «Выделение по цветовому диапазону» с разбросом порядка 20. В результате белая область внутри рамки у Вас окажется чётко выделенной. Увеличьте масштаб. Отобразите на холсте угол изображения. Возьмите «Лассо» с нулевоё растушёвкой. Нажмите «Shift» и обведите инструментом белую область в углу исходника. Повторите эту процедуру применительно к каждому из трёх оставшихся углов.
Посмотреть.
Да бы проще было перемещаться по холсту при большом масштабе с уже «набранным» инструментом, нажимайте «Пробел» – в результате любой инструмент у Вас временно превратится в «Руку», захватывайте холст и перетаскивайте в нужную позицию. Как только Вы отожмёте «Пробел», курсор снова «поимеет» прежде взятый инструмент, в данном случае – «Лассо». Инвертируйте выделение и скопируйте (вырежьте) его на новый слой. Снимите видимость с фонового (нижнего) слоя, а средний залейте равномерным тоном (можно белым, или 50% серым). На самом верхнем слое у Вас должна располагаться рамка, свободная от фона.
Посмотреть.

При активном верхнем слое создайте для такового настроечный слой (в палитре слоёв) по инструменту «Цветовой тон/Насыщенность». Для этого в нижней части палитры слоёв нажмите на чёрно-белый кружок и из раскрывшегося меню выберите «Цветовой тон/Насыщенность». В окне (оно откроется) данного инструмента двумя верхними движками добейтесь желаемой окраски Вашей рамки.
Посмотреть.
Поставьте курсор на синюю плашку верхнего слоя в палитре слоёв, нажмите правую мышь и из контекстного меню выберите «Создать обтравочную маску», тем самым ограничив ареал влияния настроечного слоя только на низлежащий.

Проделайте аналогичную процедуру с настроечным слоем по инструменту «Цветовой тон/Насыщенность» со средним, залитым равномерным тоном слоем, не забыв при этом задействовать опцию «Тонирование» в окне инструмента.
Посмотреть.

Прецезионность выделений зависит от выбранного Вами разброса в окне инструмента «Выделение по цветовому диапазону», а также – от модификаций (оптимизации, растушёвки, сжатия и расширения) выделенных областей в меню «Выделение».

Что же касается углов, то их (белый фон) можно было ещё на стадии выделения просто удалить, не прибегая к выделению с «шифтом»…

Сохраните Вашу работу по выше описанной схеме в BMP…

Успехов…