I've been shooting the 1dx for a week in cold conditions -40C/F sometimes below with the windchill.
We were 2 of us shooting the 1dx and were struggling with batteries, that is to be expected, but what is not is other photographers with former bodies (even 7d) doing better...
On the coldest days the battery did work for like 20mn before running low on voltage. So I had to turn with 3 bats, using one warming 2 up, which is annoying as you cannot be sure to be ready to shoot when something happens.
Though even when the bat indication read empty bat you still could shoot for a while as the first volts were dropping faster.
On this shooting I wasn't taking full advantage of the AF as my subjects were quite far away from me (20 to 40m), so I didn't notice a major issue with its usage. I'm pretty sure it was slower as the lower voltage would drive the lens slower, specially on telephotos. The AF was not the major concern to address there, but we were out of the working temp range of the camera, so...
The general use of the camera was slower, displays, buttons pushing (except shutter release though)... Once warmed up, a drained battery would read full charge again and the camera work properly.
Maybe you were using a neoprene cover on your camera body and not on you lens in this case you may have felt the cold effect on the usm first (that is a wild guess).
I guess the problem comes from the higher voltage that the 1dx requires compared to any previous canon body, you loose these first volts too fast in cold weather. Moreover the 1d4 bat seemed to better cope with the cold than the new one (even on the 1dx), but I haven't tested that extensively.
Hope it helped.
Cheers.