WSS 3.0 Alerts for calendar updates has stopped working for everyone. I removed and then re-added a couple alerts on one computer, they user gets the email that the alert has been added, but updates to the calendar do not generate the email alert. What could be wrong?

Have you checked the Timer Job Status in the Operations section of Central Administration?

This troubleshooting guide may help. http://sharepointalert.info/troubleshooting-sharepoint-alerts/ The very first step is to make sure you know the difference between the confirmation emails and the actual email alerts - they are sent via completely different mechanisms.