You can delete all the aliases and then re-create them in pathauto (under automated alias settings). For each user/ node/ taxonomy - click on "Bulk generate aliases for nodes that are not aliased" and hit "Save configuration" at bottom.
Make sure you have "Create a new alias. Delete the old alias." set as the update action under "General settings" (you'll probably want to change this back to "Do nothing. Leave the old alias intact" when you're done to avoid inadvertently overwriting aliases for indexed pages.
One thing to note before you do this - the aliases will be recreated according to the settings you have chosen. If you previously created any manual aliases, these might differ from the newly created aliases. This can result in a duplicate content penalty from search engines in the event that they have the page indexed under both aliases.