Rebuild all paths for a content type I want to change all paths for a given content type. 

For example is would change all node of type "image" that are currently at 

/[some_token]/[nid]


to

/photo/[nid]


I am using path auto and I have lots of node (70k), what would be the way to go ?
Like @alias suggested, you can Create an SQL query that will go over the url_alias table and create whatever aliases you want.

Note: for a small number of nodes, the answer is much much simpler:


Go to admin/config/search/path/patterns to define the new URL pattern for that content type. 
Open the admin/content page.
Filter by a specific node type.
Check the checkbox above the content item to select all the items of the certain type. 
Select the 'update URL alias' operation.
Press 'Update'.




Two other options if you have a medium number of nodes:


Temporarily change the number of nodes per page hardcoded in core. This will allow you to use the option above with more then 20 nodes at a time.
Create a VBO content admin view to allow the user to select more then 20 nodes on a same time, then select which action to execute.