In April 2009 while running WSS 3.0 we ran into an issue where users who were members of SharePoint as readers, members or designers, were not able to edit their Personal Information under My Settings (change their phone number, office location, etc.). Only users not affected were Site Collection Administrators.
When attempting to submit the change to their personal information, SharePoint would give an error that they did not have permissions.
Navigating from the home site to People and Groups, then to All People. From there, selecting Settings, then List Settings, then Advanced Settings, the Read Access & Edit Access setting was set to Only Their Own, whereas it should be set to All Items. SharePoint security takes care of the security to ensure that users cannot edit other people's information, but this is the way the settings need to be.
Changing this setting and clicking OK resolved the issue.