Could the sky on a planet theoretically be any color? The sky on the Earth is blue. Could the color of the sky on a planet with an atmosphere be of any color theoretically? 
Which colors are the most likely? 
I think it would be really awesome to have a planet with a green sky, or a red sky. 
What conditions would have to be in place for this to happen?
By the way I suspect its impossible for the sky to be white, black, grey, or brown, but maybe this is possible if not at all times during the day, a part of the day?
Does the answer depend on whether the planet is a gas planet or a rocky one? 
Initially I had in mind a rocky planet, but I suspect a gas planet allows you to cheat a little because gases can be a variety of colors (red even?).
 A: This is an extremely hard question to answer definitely; its answer is heavily dependent on three things (1) the makeup of the atmosphere in question (2) the density of the atmosphere in question and (3) the surface temperature, and therefore the spectrum of output light, of the star in question.
If the atmopsphere's gasses are themselves are coloured (e.g. $N\,O_2$), then such gasses can clearly shift an atmosphere's colour greatly. In low density atmospheres, such as that of Mars, dust and matter swept up from the surface dominates, giving the sky a "butterscotch" colour. We clearly need to know what's floating around, so we can't say much more about point (1), so I shall now assume in this answer that the gasses in the atmosphere themselves are uncoloured.
In this case, the dominant effect setting the colour is Rayleigh Scattering. This is the diffraction of light from smaller-than-wavelength inhomogeneities in the atmosphere. When you "see" the atmosphere, you are seeing scattered, not direct light from the sun in question, and Rayleigh scattering happens most strongly at shorter wavelengths. It is a powerful effect: in the small inhomogeneity limit, it varies as the inverse fourth power of the wavelength. So the process always favours shorter wavelengths.
This means that for a sun of similar spectrum to ours, and in an atmospheric density like ours, the sky will be blue, like ours, or like Jupiter's (in the upper layers). However, for very high density atmospheres, the direct light reaching the surface has its shorter wavelengths heavily attenuated by Rayleigh scattering, so that only longer wavelengths reach the surface. It is for this reason that pictures taken by Russia's Venera landers on Venus suggest that the sky has an orange glow. 
If the planet is orbitting a red giant, I am guessing this would probably mean a greenish or yellow sky for a planet with an atmospheric density like ours, as the spectrum of the star's light contains only longer wavelengths than that from our Sun. However, the inverse fourth power dependence means that now the glow from the atmospheric gasses themselves is much weaker, so the sky's colour is more likely to be dominated by things like dust, as in the case of Mars.
A: The most common colour for the sky on Earth is a white (or rather grey) sky.  Clouds cover around 70% of the Earth, and the nature by which they are scattering shortwave radiation makes them appear white or grey.  This is because photons coming from the Sun are likely to be scattered multiple times, and because the dependence on wavelength is not strongly increasing or decreasing.

White sky over Llyn Padarn.  Source: Wikimedia Commons 
Blue skies are particularly frequent on Earth:

Blue sky.  Source: Wikimedia Commons
Around sunset, we often have red skies:

Sunset sky.  Source: deviantart.
That leaves a number of other colours.  You mention green, black, brown.  Black skies occur at night or when there is dense, heavy particulate matter in the atmosphere, such as smoke.  One way to obtain a green sky is by Aurora.  One could speculate a planet where those are semi-permanent.

Aurora.  Source: Wikimedia Commons
Aurora, by the way, can also be red or yellow.  However, aurora colours are limited by emission lines of upper atmospheric gases, which are usually relatively simple molecules.  And perhaps by mixing of those colours.  But they cannot be /any/ colour.
But combining those effects?  If one can design an atmosphere from scratch, with a plausible way of this atmosphere to exist somewhere in the universe, with clouds at a particular density, aurorae dancing in the sky, aerosols perpetually present... you can create a lot of different colours.  The sky is the limit ;-)
A: Hmm... Mars has a red sky. But that's cause of the iron content in the soil absorbs other parts of the visible spectrum and reflects back the red part, so the sky looks reddish.
I do not think a blackish sky was too far-fetched cause carbon tends to be black, smoke is blackish grey. Perceived color depends on different elements absorbing different portions of the electro-magnetic spectrum and reflecting back the remainder of the spectrum. So color of anything depends on what's reflected back.
So therefore, to answer your question, the color of the sky of any planet depends on the chemical composition of its atmosphere, the incident light, and other such factors.
