Did you try, when on the controller screen, holding the menu button down unto the two middle lights are flashing on the controller?
Every now and then I have to resync my controller after syncing a ps3 controller (the ps3 controller still gets used on a ps3) and sometimes I have to reboot the OUYA a couple of times for it to work. Also you could try connecting it from the bluetooth menu in settings.