As odd as this may seem, here's what I did for a Nextel 7520:
Deleted speed dial voicemail entry for 1 or W
Cleared the device event log by holding ALT L G L G
Took out the battery, rebooted, and it worked
Every time I tried editing the number through Phone log > Options > Voicemail it would revert back to the wrong number. Deleting the speed dial entry and pulling the battery did not work until I cleared the even log. Clearing the log was the KEY.