You have 2 options:
1) Export all of the phones using BAT export, update the extensions via Excel and re-import using BAT
2) Develop SQL query and ideally push it via AXL
I've used a third party tool called "Net Packet Renumber DNs" to do this. You give it a simple text file with old numbers and partitions, and new numbers (optionally new partition and css as well). It renumbers then in place, with no unassigned DNs left hanging around afterwards.
@TONY SMITH Is this a free product? All they must be doing is just pushing SQL updates via AXL. We have built such tools allowing us to do all changes with regex, but would only be able to use our tools on an official engagement, hence I did not list it here. Wonder if the tool you speak of is widely available to everyone.