A few thoughts...
Maybe an indexing problem with one of the fields in the database. you may try importing the data into a clean clone, this will recreate all the indexing and may solve the issue. (if this works, check everything, run recover on the files, see if there is an underling issue, if there is, start looking for the last known good backup)
Could any of the security groups prevent a user from doing this reliably?
Could this be a Record locking issue (more than one person trying to use the record at once, if in a script with error capture on, you would not see it)
Thanks for the reply. I'll give these a try. The first suggestion seems to fit the symptoms pretty well. This will take a while though; 50+ folks use this series of databases daily so I'll have to figure out a weekend to get in here! Thanks again.