That's surprising. Wasn't Minecraft made in Java? You'd think the Android version would work best (after the PC one of course). Sounds to me like they just didn't care that much about the Android version.
While there's a lot of Minecraft that's certainly CPU-bound, rendering at higher resolutions has next to nothing to do with CPU speed. The bulk of your rendering work is done by the GPU, and the GPU in Ouya is more than capable of rendering Minecraft at HD resolutions.