I just figured something else out:
Make sure your Kinect has its own mains supply and is not plugged into a strip adapter or anything like that! It will not get enough power!
Mine consistently works 100% of the time now it has its own direct mains supply and is on its own USB controller.