Thanks for your response Brian.
Unfortunately the CFBundleIdentifier is not the problem. It is in fact getting past this point which I can confirm by putting in an incorrect bundle identifier, in which case I get error
[Warning] Unable to match bundle identifier "au.net.xxxxx" with AppID in all provisioning profiles
When I correct the the bundle identifier so that it matches, I get
[Warning] No certificate found in provisioning profile "xxxxAppStoreMay2015"
So it is finding the correct provisioning profile, matching the bundle ID but cannot see the certificate, which is definitely in the provisioning profile.
A similar issue reported here...
shows that one person regenerated with the profile and redownloaded, which fixed his problem.
I tried that, using a paired programmer to verify that I wasn't making any silly errors, and I still get exactly the same problem.
I have tried deleting certificates/profiles etc from keychains so that I am starting from scratch but I still cannot get past this point.