Go to the folder /documents/fritzing/bin. There you will see files like my_parts.fzb. You will also find you new bin file ???.fzb. move your new icon to the this bin folder. Open up your ???.fzb file and on the very first line you will see something like icon=“Custom1.png”. Replace the icon name with your new icon name.
If I remember right, that is how it works. You may need to restart Fz for it to appear.