I've had all 5 of my family's StarTACs upgraded at my local Alltel
store.  There was no charge.  They have to plug the phone into their
computer to download the the firmware.  The process takes about 10
minutes.

The latest firmware for the StarTAC 7869W (for Alltel, not Verizon
versions) is 7659.  The biggest difference you will see is that the
phone is less likely to fall back to analog mode in weak signal areas
or because of momentary signal disruption.  If your present firmware
is earlier than 7654 you will also see changes in your messaging menu
(what you get when you press the "envelope" key) when you upgrade the
firmware.

royc