Is the user already registered on your site before upgrading? From the way you described it, it sounds that way.
It's very important that the user is logged into his account when he loads the page with the PayPal button, because that way the button will have a reference to his existing account, so the payment goes towards its upgrade.
If no account is referenced, as is the case when the visitor is not logged in when the page with the button is loaded, then the payment will go towards a new signup, and not an existing account.
It's a good idea to have the upgrade form in a page protected at Level 0, so that only a logged in user can access it. Also good is a message in the regular payment page, saying that if he already has an account, to please log in first and then pay.
It sounds to me like the user is not logged in when he loads the page, pays, and after returning logs into his account and finds it wasn't upgraded.
I'd check if he got a welcome email with a signup link, this would be the case for payments that go towards new signups instead of upgrades.
I'd also enable logging, as Pat suggested, to help troubleshoot until you've sorted it out.
I look forward to your update.