This may sound stupid, but by default, Custom Function 01 (C.Fn-01) is set to 0. This automatically switches the flash power off after some amount of time. From the factory, the 580 ex ii switches off. If you're used to that, and your CF-01 is set to 01, it's possible that you're not flipping the power to off, in which case, the batteries will certainly drain over night. I purposely have my flash set to 01 (do not power off) because to me, I'd rather occasionally forget to switch it off (and have the batteries drain down) than have it not flash while it's on a remote trigger and a pain to get to. Like I said, I could be way off base on this, but the times that my flash has drained power in a short time has been because of this.
So, in summary, check to make sure your C.Fn-01 is set the way you want it.
0 = Auto Power Off
1 = Don't Auto Power Off ("drain your batteries when left on" mode)