You must not install NewIcons on top of OS3.5/3.9. You can use the icons but you may not install the programs. Remove everything NewIcons-related and make sure you have icon.library and DefIcons from the OS3.5 CD. Especially make sure that neither NewIcons nor DefIcons is called in user-startup and delete newicon.library from Libs.
Bye,
Thomas