For those who do not play much on eBay there was a lot of issues with purchasing controllers for the PlayStation 3 in regards to china making a ton of knock off controllers. These third-party or P3 controllers looked like a Sony PlayStation 3 controller except that if you ever picked one up and start pressing the buttons or pushing the analog stick around you know that there is something not quite right with them.
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.