Well I started the palette over pretty much from scratch with the new golem concept and got this:
I'm worried that I kind of ended up with a less saturated version of the same thing, but there are definitely better greys and purples... I just didn't manage to utilize any of the purples in these mock-ups...
Overall though I like this palette better I think.
Another question, when making background tilesets and the like, should I utilize the same palette as the foreground, or would it be wise or good or anything to use a different one: i.e. more faded with more 'off in the distancey' colors?