I have a user whose display name has been updated and now the MOSS profile database and people search shows up fine but when the user logs in the "Welcome " message in the upper left corner is still the old value and so is the data in "My settings" if you select it from the drop down menu.
How can I get these data to update correctly? (I have tried to remove the profile, add it again and do a profile import but that has not cleared the last errors.)
Two things. First, make sure that the content database is set to online (Central Admin -> Web applications -> Content Databases) and not offline. When offline user name changes do not propagate.
Since you said this is MOSS, make sure your SSP user profiles are set to synchronize on a schedule (they are not by default). Set a schedule if not set up.
You can also try to force a user profile synchronization them by running
stsadm -o sync