I have had that issue before, and with other phones too. I believe it is an issue on the carrier's side, where they do not properly convey an "all clear" message back to the phone so that the voicemail icon disappears.
I've noticed this also on other carriers and other type of phones when managing a fleet of blackberries. It should eventually go away. Sometimes it's hours, others it's weeks. You can try to follow the carrier's advice, but it may or may not work all the time.
It should correct itself, but if you're impatient... you could call yourself and leave some test voice messages, then checking your voicemail via the G1 and deleting them to attempt to have the "all clear" message sent.
Either way... Good Luck...