My 360 console developed a problem - suggesting it was overheating and therefore shutting down.

Upon replacing the console, my Kinect from the old console reports that is "connected" but could not be "verified". Any ideas?

PS: the console suggests unplugging and restarting - all of which result in no change.