Ok, figured it (fingers crossed). It was permissions set on the "newly registered users" group which everyone goes in by default.
I've removed you all from that group, and will change the default membership to the "registered users" groups which has the PM permissions enabled. We are using the forum in a slightly different way to the 'out of the box' settings they recommend! They assume not to trust anyone signing up to a forum, until they have proven trustworthy. You lot, from experience, are generally safe :ympray: