Mine so far focuses instantly in low light, but I've only been using the default center spot. My 5D MK II was also instant, but a hair slower, and the 5D MK II was one of the fastest low light AF bodies around.
I did turn off all the lights in my studio and verifying that it would not AF, then as I added light so that it needed ISO 102000 to focus at 1/60 and f/4, it took 3 or 4 seconds to AF. As the light became enough to use ISO 25600, focus was fast. I was using my 135mm L to test this.
I haven't tried the AF assist light on my 580 EX II, because it did not need it in what I considered to be extreme low light. I'm wondering if the issue might have been related to the flash unit. I'll try mine again tonight and try to duplicate your problem, it would be good to know if something is triggering this, or if your AF has a problem, or if mine also has a issue that I did not see.
I do lots of extreme low light photography in near darkness and focus is perfect and fast with my MK II, so focusing in very low liight is a must for me.