Icon.library of os3.9 already has support for newicons, so newicon.library is not needed anymore.
First make sure that in workbench prefs 'no newicons' is unticked.
Next comment out the c:newicons command in user-startup, reboot and see if your newicons show up this time.
Edit: Don't install the deficons program that comes with newicons. OS3.9 contains a newer version of deficons.
