You can also do it directly at the phone you want to change, as long as it's a display phone.
Feature 00
Left Intercom Once
Dial new name
Feature 00
For the letters, press the number that contains the letter, then dial the position of the letter. For example, to spell out DenneyM, it's 3-1 (D is on the 3, it's the 1st letter), 3-2 E on 3, 2nd letter), 6-2, 6-2, (N on 6, 2nd letter), 3-2, 9-3, and 6-1.