"Update parameters from database" adds and updates parameters, but doesn't seem to remove parameters... I guess they want you to be able to save any custom/ad-hoc parameters you might have added to components manually in schematic editor, when you do component updates. So in your case when you changed the name of a parameter and adjusted the link file to suit, you now have a dead parameter in each of the components in your schematic sheet that's no longer related to the database, and so no longer updated.
As already suggested in passing by Tim, the trick is to go into your "Tools>Parameter Manager" menu from the schematic editor, and select it to manage parts parameters only.
Then you get the whole list of every part in the project with a column for every parameter used. (kinda like a BOM, but live over your whole project's schematic sheets... Click somewhere in the parameter columns you don't want any more, then right click "remove columns" - you'll get a dialog to confirm (again stating parameter name for you to check!) and boom, that old parameter name is completely removed form every part in your project.