In the beginning of Naruto, the Kazekage wears blue clothing:
When Gaara becomes Kazekage, the color changes to green:
Is this ever explained, either by the show or by one of the creators?
As of episode 305 of Naruto: Shippuden, this does not appear to have any official word, either by the creators or in the story.
It seems that, for some reason, the garb was initially portrayed as blue in the anime. However, the official cover of volume 49 of the manga portrays it as green (the Kazekage is in the top left here, of course):
As you can see, the Mizukage should be the one who has the blue garb; this appears to be an error in the anime. However, as you noticed, it was corrected in Naruto: Shippuden episode 199 and forward.[Naruto Wiki]
This is probably because Mei (the Mizukage) has the blue hat (water is most commonly associated with the color blue), so they changed Gaara's hat to green (2 blue hats would've looked weird...)