Mine is the same and it's a pain in the arse. Sometimes it goes many days and connects with no issues and then it fails and I have to unplug/replug the adapter from its USB socket for it to connect. I have tried USB 2.0 and 3.0 and neither made any difference. I have also tried pairing the controller with a USB cable (read it works) and no difference. I have seen the same behaviour on 3 different pcs and fresh windows installs. USB drivers are up to date etc. It's just random if it wants to connect first time.
I am using an Xbox Elite controller and never had any of these issues with my Xbox 360 wireless pad. I contacted MS about it and got pushed from one department to another, in the end I gave up.