Mick, I clear the palette paths in Acad Options->Files tab, then add in a new path - this creates the .atc files and structure for you.
Then you just add icons and what not...bingo - new palette.
Store on a server and write some mojo to swap (add in the path to palette path or remove as necessary) and you're good to go.
Cheers,
Glenn.