Why doesn't frozen sugar solution taste sweet? I'll try to make this as brief as possible:

Dissolved two teaspoons of table sugar (sucrose) in about 250ml water. Sipped it, and as expected it tasted sweet. I let the rest of it sit in the freezer overnight. Next day, I took out the frozen sugar solution and, well, licked it. 

Surprisingly, I could barely taste any sugar in it. It was almost as though I was licking regular ice.

Why is it that I'm not able to perceive any sweetness here? 

I was under the impression that since the solution, being a homogeneous mixture of sugar and water, was sweet, the "popsicle" I made ought to taste sweet too (since the sugar would be evenly distributed over the volume of the ice).
Where is the sugar?

When you freeze a dilute aqueous sugar solution pure water freezes first, leaving a more concentrated solution until you reach a high concentration of sugar called the eutectic concentration.  Now you have the pure water that's frozen out, called proeutectic water, and the concentrated eutectic sugar solution from which the sugar is finally ready to freeze along with the water.  Upon freezing this eutectic composition forms a two-phase eutectic mixture, in which the sugar may appear as veins or lamellae (like veins of some ores among Earth's rocks, though these typically form form a different process).  If that structure is in the interior of the ice cube, likely since you cooled the solution from the outside, then licking the outside you got only the pure water proeutectic component.

See https://en.wikipedia.org/wiki/Eutectic_system for more about this process.

Addendum:  I tried this with store-bought fruit juice which was red in color.  Poured it into an ice tray and froze it overnight in my household freezer.  It appeared to be a homogeneous red mass and tasted sweet, but was also mushy implying some liquid was still present (after overnight freezing for an ice cube sized sample).  The juice was roughly 10% sugar by weight.