I agree that it must be a permissions issue. When we went to ArcGIS Server 10 and tried editing, the only problem we had was the 3rd party extension issue. Once we created feature classes to not be tied to this extension, it just worked. The only time it hasn't worked is when we forget to grant the appropriate permissions. I have no idea that this exists, but SDE might log when a specific user attempts to make an edit and get denied. Or you could try your edit, then go to the ArcGIS Server manager page and check the log files there.
Good luck.