I use message_notify with drupal commons. One of the preset messages is commons_q_a_question_answered. I tried to send this message via rules module without success (action "Send message with Message notify") and using the example module with a php custom action, no success too.
Do you have the same problem ? do you solve it ?
I reported a bug in the module here