Yes, it's grammatical—but in a slightly unconventional way. A sky of blue leads the listener to hear the adjective "blue" as a noun. It gives emphasis to the color in a way that "a blue sky" would not. Similarly for a curtain of green, a sea of grey, etc. You are right to notice that more ordinary grammar would make these "a blue sky", "a green curtain", "a grey sea", etc.
Writing noun preposition adjective instead of the customary adjective noun is a figure of speech—a deliberately unconventional use of language for rhetorical effect. It's a poetic device, not common in everyday speech or even in writing. Below are some similar figures of speech.*
The future was wide open. … The sky was the limit. Into the great wide open. [From a song by Tom Petty and the Heartbreakers. "Wide open" is first used as an adjective and then coerced into serving as a noun. This is abnormal grammar for poetic effect, giving concrete form to a feeling of limitless possibility.]
Go directly to fabulous. [An advertising slogan for the California Lottery. This kind of figure of speech is common in advertising, where the violation of grammar helps make a phrase memorable because it stands out from ordinary speech. This article in The Week documents many more.]
The hotelier's bank account was in the red, so he went into politics. ["In the red" is a familiar idiom for a negative bank balance. Like many idioms, it is a figure of speech. The word "red" here is an adjective treated as a noun, referring to the red ink used by accountants to record debts or losses.]
The King's name is a tower of strength. [Shakespeare, Richard III, 5.3.12. More evocative than "a strong tower". The reversed wording suggests that the King's name is a kind of source from which people can draw strength for themselves. Notice here that the adjective "strong" changed to the noun "strength". "A tower of strong" would unambiguously violate grammar, making it more jarring and hence more figurative.]
Dictionary entries for color words usually list them as both adjective and noun. One might therefore conclude that a sky of blue strictly follows the ordinary rules of grammar and therefore isn't figurative. I think a better way to understand it is that people hear "blue" primarily as an adjective but that pressing it into service as a noun is common and familiar enough for dictionaries to mention it. (The ordinary noun for "blue" is "blueness".)
Rules are a helpful crutch for beginners, but eventually one must outgrow the expectation that English works only by rules. The real principle is that we understand less-familiar forms and phrases as variants of more-familiar ones (as in any language). Three very strong, familiar landmarks in English are: "a blue sky", using "blue" as an adjective, and noun preposition noun. To understand "a sky of blue", we let "blue" slip into the role of a noun. This is easy because treating "blue" as a noun where needed is pretty familiar, but as you noticed, the clash with blue's ordinary role as an adjective is slightly odd here—just enough to make a figure of speech. The figurative meaning comes from the fact that we still treat "blue" as a modifier on "sky" but we're also influenced by many other "of" phrases, which name a material, origin, or other aspects of things felt to be deep or essential: "a sword of iron", "flowers of summer", etc.
Into the great wide open makes a stronger figure of speech because it abuses "wide open", which is normally an adjective. But treating the adjective "open" as a noun with roughly this meaning has been done enough that dictionaries mention it, so this phrase relates easily to another familiar landmark. Go directly to fabulous is jarring because "fabulous" has almost no history of being coerced to a noun, but the phrase as a whole is close enough to familiar landmarks that we easily understand it as a playful, deliberate variation.
A beginner lacks the familiarity with English needed to stray from the landmarks in a way that a fluent speaker will understand as deliberate. When beginners try this, it usually just sounds like a mistake. There can be no precise rules to learn, since by definition a figure of speech bends the ordinary customs of language.
So, here is the lesson from all this: you should master the most familiar landmarks and notice how common figures of speech, like a sky of blue and in the red, relate to the familiar landmarks that they vary. That's what enables you to leave rules behind and communicate by creatively combining common cultural reference points—the way everyone communicates in their native language.
* There are names for these figures of speech, though they are not widely known. Using a word as a part of speech that it normally doesn't play, like using an adjective as a noun, is called anthimeria. Putting a word into a different grammatical case than usual, such as making it into the object of a preposition when normally it wouldn't be, is antiptosis.