The main problem here is that you need to include a VertexTextureCoordinates (VTC) in the Polygon for a texture to be applied. However, the rest of the problem is not as simple as it seems. Here's the output of my approach. Below it, I discuss texturing several polygons belonging to the same country, according to their timezone. You can also skip that and jump straight to the code block.

Handling textures for several polygons
CountryData[country, "Polygon"] will give you a list of polygons that depict the main boundaries, but is not necessarily contiguous. This differs from country to country — for example, Alaska is not included for the USA, but Tasmania is for Australia. Since they're sorted by area (at least, that's how it seems to me), you could simply pick the first to get the largest land mass, but it looks weird in cases such as New Zealand, Canada, Indonesia, etc.
However, the polygons returned are in the formPolygon[{poly1, poly2, ...}] and you cannot provide VTC for all of them at once. So you'll need to split the polygons and supply the VTC for each. If we naïvely follow the documentation and try something like the following (zoneTexture is defined later, but is not necessary to understand), you get:
With[{country = "Australia"},
p = CountryData[country, "FullPolygon"];
c = CountryData[country, "FullCoordinates"];
z = zoneTexture@CountryData[country, "TimeZones"];
];
Graphics[{EdgeForm[Black], Texture[z], (Polygon[p[[1, #]],
VertexTextureCoordinates -> Transpose[Rescale /@ Transpose[c[[#]]]]] & /@ Range[Length[c]])
}]

Doesn't seem so bad, except when you look closely, you'll notice that Tasmania also has the same texture as the mainland — i.e., not coloured per its time zone. Now this can be easily fixed. You just need to get the extents of the country's boundaries and rescale the VTC to range from 0 to 1 within those extents.
Code
The following code will generate the image above. Note that I use the image available in ColorData using the "Image" option, and index it directly to obtain the texture. This avoids having to convert it to an Image, which can slow it down. Texture rasterizes objects anyway, so nothing is lost here. I also resize it so that it covers some cases where you observe white gaps.
Begin["ZoneMap`"];
image = ImageResize[ColorData["Rainbow", "Image"], 1000];
zoneTexture[zones_] := If[Length[zones] == 1, #, ImageRotate[#]] &[
ImageTake[image, All, Clip[Floor[1000 {#1 + 12, #2 + 12}/24], {1, 1000}]] & @@
Through[{Min, Max}[zones]]
];
CountryGraphics[country_] := Module[{
coordinates = CountryData[country, "Coordinates"],
polygons = CountryData[country, "Polygon"],
zones = CountryData[country, "TimeZones"],
minmaxlat, minmaxlong},
{minmaxlat, minmaxlong} = {Min@#, Max@#} & /@ Transpose[coordinates~Flatten~1];
Graphics[{EdgeForm[Black], Texture[zoneTexture[zones]],
(Polygon[polygons[[1, #]], VertexTextureCoordinates ->
Transpose[{Rescale[#1], Rescale[#2, minmaxlong]} & @@
Transpose[coordinates[[#]]]]] & /@ Range[Length[coordinates]])
}]
];
End[];
ZoneMap`CountryGraphics /@ CountryData["Countries"] // Show
Now this works fairly well and you should be able to replace zoneTexture with whatever you'd like.
Extending to "FullPolygon" for the countries
This can also be extended to cover the full boundaries of a country, i.e., including unincorporated territories by choosing "FullPolygon and "FullCoordinates" in the respective calls. However, it fails for 2 countries (to my knowledge): USA and Russia. The reason it fails is because there is no equivalent "FullTimeZones" that will return the full extent of the time zones. Hence, the rescaling stretches the time zone map for the primary regions all the way across the entire extent. For example, in the case of USA, Guam, which is near Australia, forces the texture to stretch from there onwards. It is worse in the case of Russia, because the far east tip of the mainland lies in the Western hemisphere, resulting in:

One would also expect a similar scaling problem for the UK, but Britain still has the same colour since there is only one time zone. In this case, the territories are also coloured as GMT, but they're tiny anyway. Since there are only two cases that stand out visually, they can be handled individually, which is left to the reader.
CountryData. Like:Graphics[CountryData[#, "Polygon"] & /@ CountryData["Continents"]]. – István Zachar Mar 28 '12 at 19:27FullPolygon… Antartica isn’t either. – F'x Mar 28 '12 at 19:29TextureneedsVertexTextureCoordinatesto be applied on polygons. – VLC Mar 28 '12 at 20:33