@Nadious - Yes, the PS3 wireless controllers perform better. I believe they use a different BT protacol, Ouya went for energy saving, PS3 didn't. The Xbox 360 wireless controllers don't work with the Ouya, unless you have a USB dongle, which I don't.

It's interesting that this comes up again. I had terrible lag in july and august, the updates helped a little, my new controller (through RMA) seemed even more solid. The last couple days, my lag was really bad, and I thought maybe I had been too optimistic.

Now it seems like it could be a new issue that introduces the lag again for several people. I noticed that my connection is very dependent on line of sight. Where I had a slight disturbance before, e.g. when the controller sank beneath the table, the Ouya gets NO signal right now. None whatsoever.

I'll try new batteries, but since it comes up with you guys, too...
Do you also have the impression it's gotten worse since a couple of days (up to 2 weeks, wasn't playing much)?