Check the xf_user_upgrade_log table. Is there any record of the transaction? The record may contain a specific error message if there was a problem. If there is no record of the transaction then make sure the payment completed (in your paypal account). Also check these things:
1) Make sure your board URL is correct:
Admin CP -> Home -> Options -> Basic Board Information -> Board URL
2) Note that the paypal callbacks don't work if your forum is behind a htaccess login.
Or it's possible Paypal simply failed to send the callback. That happens sometimes in which case you can manually upgrade the user in the Admin CP.
So it might be to do with the paypal email address I'm using. It appears I need to use the "parent" one, and not a child one. I know I have two paypal email addresses linked to the same account, so I'll check I'm using the original one (which I presume is the "parent" one).
# Aha... When I go to Users > Transaction Log, and check one of the errors, I get this: