This was posted some time ago, but it comes up as one of the top results on a Google search, so I thought I'd post a reply to save others some time. I had this same issue until I copied jbossmq.jar (from JBoss 4.2.x) into my JBoss 5 $SERVER/lib directory. The hint came from the JBoss Messaging installation guide, section 4.6.1, found here:
http://docs.jboss.org/jbossmessaging/docs/userguide-1.4.1.GA/html/installation.html