Hi David,
When I have done this in the past, I have used Import/Export > Export then choosing 'Phone' under 'Device Data' to export all of the devices instead of going through the BAT > Phones > Export Phones > All Details menu. This will include everything about the device that is in the database.
You can then just remove all of the entries that you don't want to update, then edit the directory number field and 'Import' them back into UCM. When you do the import, either delete the phones ahead of time, or select the box for overwrite existing configuration.
If you haven't used Import/Export before, you will have to re-tar the file before uploading it to UCM
Thanks,
Adam