It's in the signal.
The clock is the same way. When phone is off, the clock does not keep
the correct time.  It's set when your phone boots up.

A. Startup and shutdown screens are typically graphics stored in phone
memory (firmware), thus are not affected by the network or the SIM, and
are typically changed only by updating the firmware, usually only by
cable, although some newer phones can be updated OTA (over the air).

B. Text on menus is also stored in phone memory (firmware), and thus
isn't directly affected by the network, although it can be overridden by
the SIM, which can be re-programmed OTA.

C. GSM/UMTS rules for network display, sometimes referred to as
"operator text" or "alpha tag", but more accurately:
  * Public Land Mobile Network (PLMN) name, or
  * Mobile Network name (shortened form of the above), or
  * Service provider name (SPN) (as stored on the SIM),

1.  If Mobile Country Code (MCC) and Mobile Network Code (MNC)
    broadcast on the network match the MCC and MNC on the SIM, the
    Service Provider Name (SPN) on the SIM is displayed.

2.  If the MCC-MNC combination does not match, the phone checks a table
    in its firmware for an entry corresponding to the MCC and MNC
    received.  If found, that entry is displayed.

3.  If no table entry is found, the country abbreviation (or the MCC if
    no country name entry is found in firmware) and the MNC are
    displayed.

SIM programming can be updated OTA, so the Service Provider Name can be
changed.  Since that is done on a per SIM basis, different phones may
change at different times.

What AT&T/Cingular is apparently doing is reprogramming SIMs over time
OTA with a new Service Provider Name, but not (yet at least) overriding
menus and/or updating phone firmware.