Which of your systems is that ? WB 3.1 or WB 3.9 ?
If WB 3.1, is FBlit installed and has it the correct configuration ?
The latest icon.libraries are checking if FBlit is running before they switch to FastMem on WB 3.0/3.1. This was different with 46.4.228, it was always using FastMem as default memory.
If you use WB 3.5, then you can put the command WBCtrl ICONFAST into the startup-sequence just before LoadWB. And WB 3.9 has the Workbench preferences where you can choose FastMem (other memory) for icons.
If really nothing seems to work then try this (I did not check it out yet because my Pizza and Red Wine are waiting)