The solution you described for bluetooth pairing does not work on PS3 and P3 controllers!
PS3 and the third party "P3" controllers operate a little differently when it comes to their blue-tooth enabling. The first thing you have to do with that model of controller that you hard-wire it into your Ouya (by "hard-wiring" I mean using your USB charging cable that you normally have hooked to your PS3 and hook it from your Joystick to the Ouyas USB Port). By hard-wiring it it breaks any pairing with another PS3 that could be in your house or perhaps a PS3 that is long since separated from the controller as you may have bought this online somewhere.
Note: Upon plugging the PS3 controllers into your Ouya, the Ouya will respectively disable the Bluetooth service on the console and you will lose connectivity with your Ouya Controller. This is perfectly normal! Just make sure that you can navigate around the menus with the wired connection.