A user reported this problem which I've verified:
2 Users are both in the same Profile Type. That Profile Type has a custom field (AcyMailing).... one of the users sees it when they edit their profile, the other doesn't!
Also the reason this was reported was the user who doesn't see this field was trying to edit her profile and it kept saying not all fields were completed. The one that wasn't was the one that wasn't even displaying for her... so she'd have never known! (I've since switched it to non-mandatory and verified she can save her profile now)
Any idea where I could look to solve, or will you need access details to look into this one?
UPDATE: I've added a user account to the 'additional info' on this ticket you can use to see that the AcyMailing field is not showing up on 'Edit Profile' - This seems to be affecting new users (perhaps that's a clue?) - older user accounts I've tried DO see it on 'Edit Profile'