Добрый день.
Достаточно сменить favicon.ico в корне вашего сайта (или по пути, указанному к нему в коде страниц) и дождаться переиндексации поисковым роботом Яндекса. Через некоторые время (в течение двух недель) новая фавиконка отобразится в выдаче.
Ждёмс...
Тоже такая проблема встречалась. Эксперементировали на сайте смосервис медиа. С РосМедиа такой проблемы не наблюдалась. Как вариант в Яндекс Вебмастер это добавить. Может получится.