I've had this happen to me before, and I've found that it seemed to always be related to missing one or more setup parameters for the QCF or the JMS Provider. For instance, take a look at
Sheldon Wosnick's MQJD Article. Yes, I know you're using WebSphere MQ instead of MQ-JD, but going through his setup and making sure you've entered something in everywhere he has is a useful exercise. It's saved my butt a couple of times.
Kyle