However, some icons cannot be changed simply by cutting and pasting. I am not sure mail.app is one of them, but Omniweb is. If you see that pasting does not work, go to the application, right click and select 'Show contents'. Then look for the icon file, with the ending .icns Replace it with a new icon - which must also be a .icns file.
I also noticed that some icons change only after a logout and even after a restart (Yahoo messenger for example)