Well this sounds like the problem I was having too. From what written above though, the payment arrives before the new account is created. Therefore, if the Payment Complete triggers the order change, then the role cannot be assigned because the new user hasn't be created yet. But if the Checkout Complete triggers the order change, then it looks like by then the new account has already be created and therefore the role can be succesfully assigned.

So try disabling the current profile and create a new one triggered by Checkout Complete instead of by the Payment Received.

It'be great to have some kind of pictorial illustration or flowchart of the actual workflow events in the documentation.