Hey,
I had a similar problem with a quadraped rig. Basically yor paint weights for some joints are not 100%. So as Mat suggested go througheash joint and ensure that the weights are 100%.
Nice tip on the Multi colour, never tried that.
Chris (formerly R@nSiD)
Twitter
When the power of love overcomes the love of power the world will truely know peace - Jimmy Hendrix
Winner SM VFX Challenge 1
3rd Place SM SteamPunk Challenge (May 2007)