GHTROUT's suggestion would be ideal as long as the 4 digit numbers that the CO sends do not conflict with any of your existing 5 digit numbers. You would have to use Incoming Digit Conversion to convert the 4 digits to 5 digits. You could probably even convert the new 6xxxx incoming numbers to your old 3xxxx DN's. But then you will always have that mismatch between internal and external dialing.
OTM has a cool Global Update feature called ADN (All DN's).
In Global Update select the ADN (All DNs)feature.
You can then enter 3* in the Old Value box and 6* in the New Value box.
This will not only change all the SCR and MCR keys but also the FDN's, HUNT, ADL, CFW, MWK etc. I have found that TM (vs. OTM) does not do the FDN's and HUNT but it is still easy to do a Global Update on those separately.
Synching the changes to the 81C is still a huge task.
You will need to change any ACDN's for voice mail etc. that are in your DID range. All the changes will problably not take on the first synch since you will have some TN's that FDN or HUNT to phones that haven't been updated. You will probably have to run several synchs to complete all the changes.
With the 81C you could split the CPU's and do all your changes on the inactive core, then cut over to the newly programmed core. This will reduce your downtime from many hours to a couple of minutes.