Just laying some foundation:
I've always kept the toolpalettes on a separate drive (easy access to the files, not that you need to access them much) like so:
T:/ToolPalettes/Toolpalette-Layout (aka "the T-Drive" located on the server)
I have also created and populated NEW toolpalettes so as to not overwrite AutoCADs default palettes.
I have never needed to add the paths to the file locations other than in the "Tool Palette File Locations" in Options (Files Tab)... not saying that Coloradomrg's suggestion is invalid... just that I have not had to.
Can you tell us more ?
What version of AutoCAD are you using ? are you using LT ?
Are you modifying default TPs or creating new ones ? If new, what is the process you are going about this ?
Did you just do a basic search for information on TPs (there is lots of info on TPs). I have posted allot of questions myself and pretty sure I have posted solutions to the was it worked for me. You can try reading some of those posts. Sorry at the moment, I do not have the time to find the right one for you to read...
But, If I recall:
Create a folder named what you want to name the TP... and where you want it.
Get the path somewhat like I am showing above (your location will certainly be different) and paste that into the "Tool Palette File Locations" on the Files tab.
Then Ctrl+3. Should give you a blank TP.
Populate it with a couple blocks, close the TP (Ctrl+3), close CAD.
Launch CAD, Ctrl+3...
Are the things you put on there still there ?
Good luck.