Just a wrap-up of what the problem was -- it was indeed a bad battery. Even though the voltage on the battery read OK after a charge, there was a bad cell. I found it by doing a specific gravity measurement on all the cells. The good cells measured 1.250 while the bad cell measured 1.135. I took the battery back to AutoZone and they replaced it without doing any further testing on it. So far, no further issues with the battery.

isn't it nice when you have to do Autozone's work for them, anything that has 12vt is good to them