However, updating the format will not retro-actively update the full-name field for existing records so if your organization has the need to update the full-time format, you will need some manual intervention to make sure existing records abide to the new format. There are some posts suggesting to execute SQL scripts to update the existing records; however, SQL scripts are unsupported and also not possible in CRM Online. You just need to execute the following code which will take care of updating existing records to conform to the current full-name format in your organization:
Note that the only thing that I am doing is executing an Update request for each record, without modifying any attribute but it will force the full-name field to be re-calculated based on the new format. When it is so simple to correct it in a supported manner I wonder why complicate life with SQL scripts!
Note that I am using PageInfo because there might be more that 5000 records of each entity so the query results are paged. Thanks Andriy for pointing it out!