For a cold dessert, I often like to freeze a cup of grape juice and then eat it with a spoon like an Italian ice. What is the appropriate bracha to say before and after eating this delicacy?
I don't know for certain (CYLOR, of course), but some possible relevant sources:
Rambam (Hil. Nezirus 5:2) groups together wine and "coagulated wine," classifying them both as "fruit" (as opposed to vinegar, which is considered "waste products of the fruit").
In a few places the Gemara also refers to "coagulated wine." Two of these (Sukkah 49a and Me'ilah 11b) are referring to the residue remaining in the drainpipes (shisin) under the Altar, which was cleaned out and burned "once every seventy years." The other two (Sukkah 12a and Sotah 48b) speak of "coagulated wine that comes from Senir" - which might indeed be the same as your delicacy, as Senir is Mount Hermon, which is snowcapped all year round. Evidently, though, even when solidified it can still be called "wine."
Based on all of this, then, it would seem that freezing grape juice doesn't downgrade its status, and it should keep the same berachah. (Indeed, freezing it is less of a change than drying it out, since frozen juice will melt but dried-out wine can't necessarily be reconstituted.)
(Incidentally, if "coagulated wine that comes from Senir" means wine ices, then you've rediscovered something quite important; the Gemara in Sotah there says that this hasn't been available since the destruction of the first Beis Hamikdash!)
"There is a huge machlokes in the Poskim regarding exactly this issue if grape juice only maintains its special status as a liquid or even when hardened. Therefore, it would be ideal to make borei pri hagafen on liquid grape juice and shehakol on something else before eating the ices. In the likelihood that this is not practical, one should say shehakol." http://revach.net/ask/article.php?id=1205
"Grape Juice Ices: According to The Halachos of Brachos (Rabbi Binyomin Forst, Shlita), "Frozen grape juice (i.e., grape ices) or wine may have lost its status as wine since it was transformed into solid food. One should therefore not recite a Borei P'ri Hagofen either on frozen wine or wine that was thickened into solid form."" http://www.aishdas.org/avodah/vol09/v09n080.shtml
"The proper bracha for grape ices is Shehakol. (Laws of Brachos p. 313)" http://www.mevaseret.org/mmy/searchshiurim.php?shiur=259