WARNING: Watch for double charges when paying with a different card than you reserved
I'll toss in my experience, since the thread and title seem to imply that this is an issue limited to using debit cards and/or changing payment methods. It's not.
I use my Discover card for rentals (sub-optimal, yeah let the cc hounds descend upon me), and I've been having the same billing issue, to the point where my credit used is supposedly 3x what my actual balance is. Luckily it doesn't pose a problem financially for me, but I will be calling discover shortly to see if they can fix this up for me.