Tutorial on developing Java based Domino/MQ solutions
http://www-106.ibm.com/developerworks/edu/i-dw-ls-dommq-i?S_TACT=103AMW13&S_CMP=LDD
The problem was that we did not include all the jar files in the JavaUserClasses in the notes.ini, i.e
For the Java agents to call WebSphere MQ, you need to update the Java user classes parameter in the Notes.ini file for the Domino server. Shut down the Domino server, add the following line, then restart the server.
JavaUserClasses=C:\WebSphereMQ\Java\lib;C:\WebSphereMQ\Java\lib\com.ibm.mq.jar;
C:\WebSphereMQ\tools\java\base\;C:\WebSphereMQ\Java\lib\connector.jar;
C:\WebSphereMQ\Java\lib\jta.jar;C:\WebSphereMQ\Java\lib\providerutil.jar;
C:\WebSphereMQ\Java\lib\com.ibm.mqjms.jar;C:\WebSphereMQ\Java\lib\ldap.jar;
C:\WebSphereMQ\Java\lib\jndi.jar;C:\WebSphereMQ\Java\lib\jms.jar;
C:\WebSphereMQ\Java\lib\fscontext.jar;
For this example, we've assumed that WebSphere MQ is installed at C:\WebSphereMQ\; obviously, you'll need to change this to match your environment.
Also you only need to include the com.ibm.mq.jar file in the Java Agent