For what it's worth, I've had a kobold in my game. I nerfed shifty to a free action encounter power that lets him shift as a minor until the end of his next turn, with a paragon tier feat to make it at will. It's a nice power, and a little more than I want to see a PC have at heroic (same reason I don't allow dark-vision at level 1), but it's not broken. It's not even close to what a half elf can do with Versatile Master, and kobolds have no other feat support.
These days ranged PCs have to go out of their way to provoke AoOs, so shifty is mostly extra flanking options. Again, compare it to something like permafrost, not really close.
The only legitimate issue it can really lead to is dead-zone prone (leave an opponent 1 square away and prone so they can't stand and charge). And if players want to abuse that the window's already open elsewhere, it's just a little easier. Since it's literally all the race has I can't say it's overpowered.