Here’s a tip for color: You don’t really need a palette, per se – you more need an understanding of how colors are related. I find the HSV color space much easier to work with than RGB. Also, you want to use floating-point values, not hex codes.
With HSV values, finding a related set of colors is easy. Pick a base color, and then derive subsequent colors by varying S or V. You can even do this programmatically inside a shader/material.
If I had made your ice effect, for example, I would have picked a blue-ish color, then adjusted V to get different intensities. The most intense piece of the trail is the highest value of V (note you can use values above 1.0 in most CG systems). The least intense is a much lower value of V. That gives you a gradient.
Adjusting the saturation (S) is useful for tinting. Take a base color, and multiply it by a desaturated version of another color. Or brighten a color by adding the desaturated version of another color.
Give that technique a try!