Had a similar problem with portraits and was told instead of pasting over them to use the Clone tool in your paint/photo program and clone your new icons over an existing one. Dont ask me why or how all I know is what I was told and it solved the problem for the portraits anyway. Good Luck