Thanks for the link to the article. After reading it and talking to our sys admin, I think that we've got an issue with group policy, and that the right to log on as a service is being revoked for the arcgis user account. I've got a ticket in with our IT department, and a ticket in with ESRI. If I come up with a solution, I'll post it here.
On a side note, we discovered that if we add the arcgis user account to the administrators group, the ArcGIS Server service starts up with no problem. Unfortunately, IT won't allow us to keep the arcgis user in the administrators group. If you know or can think of any workaround, I'd be happy to hear it.