Thank you for trying Messaging.
The problem you noticed has a very simple fix: shutdown the "messaging" JBoss instance, delete the "log4j" directory from $JBOSS_HOME/server/messaging/deploy/jboss-messaging.sar/org/apache and re-start JBoss.
This is the explanation for the problem: when used with JBoss 4.x, Messaging is deployed in its own classloading domain. This is necessary in order to take advantage of the latest features in Remoting and AOP, not currently available in JBoss 4.x. For that, we bundle the libraries Messaging uses and deploy everything in a separated classoading domain. log4j shouldn't be there. Removing it from the scoped deployment and using the one from $JBOSS_HOME/server/messaging/lib fixes the problem.
I will modify the release scripts to produce a SAR that doesn't include log4j and any other unnecessary library. The real issue, to which I need to answer, is why our tests did not catch the problem before release.