Step 1, review all radios in the network to see what's required to make them narrowband compliant (simple program change to replace the radio).
Step 2, order the replacement radios, if necessary.
Step 3, submit application with FCC to modify the existing license(s) to add the narrow-band emission code.
Step 4, cycle through the capable radios to duplicate the existing channels, but have the emission set to the correct narrow-band settings (instruct the users to ignore the new channels for now).
Step 5, replace any existing radios with ones that are narrow-band compliant, if necessary.
Step 6, (should be done during a period of minimal activity and when critical communication is also minimized) instruct users to use an alternate channel and reprogram the repeater(s) for that channel to use the narrow-band setting.
Step 7, instruct users to change their radios to use the narrow-band channel number(s) and no longer use the original wide-band one(s).
Step 8, cycle through the radios and remove the wide-band programming.
Step 9, (once all radios are successfully using the narrow-band settings) submit application with the FCC to remove the wide-band emission code settings from the license(s).
This process can be done by frequency, area, or some combination to guarantee functionality as necessary (steps 6 & 7 at least). If you do stagger the conversion, clearly instruct the users on the correct channel to use for which area and stage of the conversion process to reduce the chance that a wide-band user is on a narrow-band channel and vice-versa.
Please be aware that in 99.999% of the cases, the narrow-band channel will be the exact frequency as the wide-band channel. What's required with the change to narrow-band is a modified emission setting, the frequency will not need to change.
In your example, a wide-band mobile and a narrow-band base, both would use the exact same frequency, but the mobile would use a wider bandwidth than the base would (like an 18 wheeler and a Smart Car both driving in the same lane on a highway). They would both probably be able to communicate, but there may be some volume issues or audio distortion during that conversation. If done as I indicated above, they could simply both switch to the same channel setting to remain either both wide or both narrow for that conversation and communicate without issues.