Customer checkout issues

Wondered if anyone else has been having problems with this, or if anyone has suggestions.  When one customer has a problem, it's easy to attribute it to "user error", but I've had five now in less than a week, so I think it's a genuine glitch of some sort.

Customers are able to shop normally, but when checking out, they have one of the following two issues:

a) The first-time customers can't get past the checkbox for terms and conditions - it keeps refreshing the page with the box unchecked each time they hit "continue"
-or-
b) The repeat customers get to the screen asking them to verify their billing address, and when they click "continue", it kicks them back to that screen endlessly and won't let them go further into checkout.

I've asked all of them about their OS and browser, hoping to find something in common, and the only thing I've come up with is that all of them seem to be using recently updated browsers.  One was using Firefox 6, and switching to IE allowed her to finish her checkout.  Another was using IE9, and switching to Firefox (she didn't know what version) solved her problem.  Two were using Firefox 6 and didn't have access to a different browser, and the fifth was using Chrome (which apparently keeps itself updated). 

In all cases, if the customer was not able to access a different browser to complete checkout, I was able to go in through the admin panel, pull up their saved shopping carts, and finish the orders without incident.  However, I do NOT use the most recent browser versions - I have Firefox 3.6.1, and IE 7 - except for Chrome and Safari.   I have attempted to reproduce the error on my end in Chrome and was not able to do so.

Thoughts?

We're having the same issue on our ProductCart store, which was recently moved to new server hardware.