Don't know if this is best practise but works for me.
On XP I re-enroll manually if the tool doesn't seem to be doing it.
Some of these are hidden folders. Go to Tools, Folder Options, View and Show hidden files
Stop the pgptray and go to
c:\documents and settings\username\application data
Get rid of pgp corporation folder
c:\documents and settings\username\local settings
Get rid of pgp corporation folder
And in My Docs
Get rid of PGP
Remove them from the User Access part of PGP Desktop.
Reboot and login with another PGP user setup with access on that laptop.
Then readd the user and it should re-enroll them when they login.
See if they then get added. If not might need to call Symantec.
What version are you using? I know this happened on our older version and we had a consultant in to do the upgrade. And he sorted out the issue with the user not being readded when we had the same issue.