Does a user have to have the "Modify All Data" permission in order to be able to mass update records? I have a user that does not have this permission explicity set and is unable to mass update records.
No. HOWEVER, in list views, all records must be of the same record type for any mass-update abilities to be seen by any user. Can YOU do mass-update activities on that list? If not, then your list has multiple record types.
If you can, then your user will need the "Mass Edits from Lists" permission, which is included in Modify All Data, but can be assigned separately.