The only icons I've changed is the hard disk icons (system, work, games, and so on)
The reason Protracker runs from the floppy is because the tool knows where all the associated files are. Associations like these can be assigned to get over the issue. The later version of the OS also could replace your C folder and so you lose a lot of the tools needed. You may have a folder called OLD somewhere lurking in Workbench.
Just get SnoopDOS off Aminet and run it. The tool lets you see which libraries, tools etc that fail to open. Hopefully you also have DOpus so you can check to see which tools reside in say in your C drawer.
I get this when I try to use stuff off my OS3 Amiga with the OS3.9 machine. Even the simple stuff like 'more' are not in the folder. These tools get loaded in when you install the programs. I doubt it is an assign issue though you may also want to check if your user-startup has been changed.
Just a tip.. when you do change anything just make a back-up of your Workbench partition. Its so small you can probably put a copy in your Work partition. And then use DOpus to copy back all your lost tools, libraries etc. Also keeps a copy of your user-startup.
I had an issue with 3.1 once on a 4000 which I have where it installed the Workbench in a secondary folder in my original Workbench partition. And I did get all these problems.
Last tip and that is to keep your own Amiga Repository of every tool and library that you have ever used. Always useful to drop in a disk and replace the lost file. Thats what I do when I get one of these error messages. I also tend to reinstall the programs. Gives them a healthy new lease of life.
All good fun.