I know it is a bit after the fact as well, I had the same problem and finally solved it by changing the keys.
In Moodle>Network>Settings I deleted the current key, created a new one and copied it. (Don't know if I had to do that as maybe I could have just copied what was there but I did.)
I then went to my Mahara site and clicked on Administration>Institutions> I clicked the edit button for my Moodle site > clicked on the XML-PRC link next to authentication plugin (creates a pop up) > Pasted the new public key I created for my Moodle site > Submitted the changes on the bottom of that page > Submitted the changes on the bottom of the institution page - and walla it finally worked!
Hope someone finds this useful...as I wasted a couple of hours on this.
Tzvi