I, too, have seen these deadlocks. They have been happening in my application even though I'm not explicitly running statistics or compressing the table. I found a workaround by reducing the statement cache size to 0. This isn't as bad as it sounds, because your application can maintain a reference to the PreparedStatement JDBC object (one per thread) and thus avoid compiling the statement for every query.
I created an issue for this, DERBY-4279, which you can consult for more on this issue. Jeff
