Exactly what got you to this problem might be hard to figure out, but one thing seems to be apparent - you have some tool palette definition problems. I have found that if you point to a network folder of shared palettes, users have to be kept from having write access to it so the definitions don't get overwritten if they make changes. I suppose that you blocked write access, but there are other places that the individual users store their own definitions. Did you migrate? if so, your definitions probably came from previous versions on their own systems and there could be discrepancies. I have had a number of encounters where users point to several folder paths, and i run into trouble getting a particular tool, or entire tool palette definition corrected because the definition source gets hard to isolate when there is multiple AcTpCatalog.atc files involved.
I assume that all of your users are using the roamable root prefix path (AutoCAD default path for tool palettes within the windows user tree) as their first path, then maybe they point to your server standard palettes path, then they add the multiple paths to any other tool palettes that they have developed. I would back up the ones that you care about (Export them to a folder of definitions), then do a flush, then start rebuilding from scratch. What I mean is, after exporting the ones you want, with AutoCAD pointing to only one tool Palette file location folder, remove all tool palettes (yes, delete them even though AutoCAD asks "Are you sure?"), then close AutoCAD. Closing AutoCAD saves tool Palette definitions to the AcTpCatalog.atc master reference in whatever folder you left toolpalettes mapped to. Then launch AutoCAD and customize the tool palettes, importing them one by one from exported definitions. If you want to be real sure that you have this right, start with only one path for your tool palettes folders in Options>Filetab>Tool Palettes File Locations, and make it a new one. Once you rebuild your complete tool palette group from importing every palette and you are sure that each tool is right, you can close AutoCAD and copy the entire tool palette file folder to the server and have everyone point to it at a locked folder location. Then they can add any additional paths to their own custom folder on their hard drive. The key in the process is to make sure that the roamable root prefix folder isn't containing mixed up definitions of your tools, palettes or groups. That's why I recommend effectively flushing a system.
Since they are having problems with locally stored folders, I would flush their systems and have them import/create their custom palettes, pointing to just their own local tool palette folder, then once they like what they have, export them (in order to save them to a backup location). One they have backed up their definitions, they can add the standard network folder and bring in some/all of your enterprise palettes. Do watch out for duplicate palette, group or tool names though. Those will ultimately cause this issue to reoccur.
HTH,
Ron
ADN CAD Developer/Operator