The only way to get to the bottom of the issue is to obtain system logs from the ouya.
You need adb installed on your PC and then run adb logcat > file.txt. (ConnectYa also has the feature to take logs). Upload this file here. (maybe zip it first, that will make the file much smaller).
The question is why.
Can you download that file in your browser?
Do you have some kind of network filter that requires devices to confirm some WiFi login page?
What happens when you open http://statics.ouya.world/ in the ouya’s browser?
It has now strangely just started working. i.e. Successfully downloading and installing all the games I’ve tried so far. I’ve changed nothing on my network. Maybe something my ISP has done?