Had the same problems as others have reported after upgrading to joomla 1.09 and fixed thanks to suggestions in other post, however have just noticed another strange thing.

If trying to send a message from the main component the user becomes logged out of Joomla and the message isn't sent!

It works fine sending messages using the cb plugin buty not with the main component. Never noticed a problem before so am assuming its since upgrading Joomla.

Hope the author comes back soon none of the other messaging systems are as good as this