Thanks. We had done that, but more importantly I believe we have found the problem. We were doing a select with update and had locked another table by doing this (through a join) and did not take that into account. We've changed the syntax and are not seeing the problem.
Thanks again.