I have the same problem with the generic icon for Safari 5.1.8 after the latest security update for OS 10.6.8.
The "Get Info" icon-copy-and-paste trick (after copying the compass icon from an older Safari version from my Time Machine HD) won't work because this version of Safari won't accept "Paste" (it's grayed out in edit menu). The Permissions are fine, BTW.
The other odd thing with this version of Safari is that several of the customizable items for the Toolbar (like "New Tab", "Home" and "Top Sites") are now uniform silver buttons. Clearly a glitch that needs to be fixed.
What I did in the end was to download a Safafi (or Safari like) icon from a site that offers various free options. I the went through the "Get Info" performance but this time I "cut' the new icon (rather than 'copy') and that ungreyed the paste option and allowed the new icon to take up residence!
Maybe I just got lucky but worth a try.