Hi all,
I figured the solution lies in between all the replies. What I've found out so far:
1. Region / Time: One of the reasons Apple TV (henceforth ATV) wouldn't connect to iTunes Store is if it's region selection doesn't match your current Address. Secondly, if Apple TV system time doesn't match Internet time, it still wouldn't connect! Sadly ATV doesn't allow user to set its time, it does that automatically from Internet.
2. Router: most routers firewall the ports that are required to update location and time. And so if your ATV System time remains UNMATCHED, iTunes is not going to connect, as mentioned earlier.
So like mixing two bright suggesruins given earlier, 'Restore' the ATV using its menu, and then when it comes alive, connect it to your iPhone's HotSpot. Set 'Region' now (manually or automatically, it doesn't matter), System time will update automatically.
Once done, sign into your iTunes Account. And voila! it should work!
One last step: after confirming the Sign In and all Home-screen icons appearing, remember to disconnect the ATV from your iPhone's Hotspot and connect it now to your regular wifi.
Hope this solves and explains to many! It's albeit sad that ATV doesn't actually tell us what's wrong apart from just complaining: "Cannot connect to iTunes Store". Apple, is better than this!
All this is left to your discovery and your glory! You're all welcome...