i've only noticed this with a few apps. normally a reboot or logging out and back in solves this. also, make sure the program isn't running while attempting to change the icon.
you might also try just pasting over the top of your previous custom icon rather than cutting it first.