I have a Nexus S from Sprint and set it up with Google Voice. Unfortunately when I was getting Google Voice set up, I tried calling my number and leaving a message from another phone. This voice mail got put on Sprint’s voice mail system. When I switched over to Google Voice, my Sprint voice mail was deleted, but it continued to send me notifications of the voice mail.
So if you are looking at switching to Google Voice, be sure to make the switch when someone isn’t likely to leave you a voice mail. Sprint tried all kinds of things and eventually said I needed to reset my Nexus S back to factory settings. They said that the problem was on the phone because Sprint wasn’t sending out any type of voice mail notifications to me. I wiped it, turned it back on and immediately got the little tape recorder notification from Sprint voice mail.
There are things I like about Sprint, but sometimes it seems like their whole system is a piece of alien technology and works most of the time, but they have not idea what is going on or how it actually works.
Finally I went into www.google.com/voice and disabled the Sprint/Google Voice integration. The Sprint Voicemail notification went away within a few minutes.
I had to wait 15 minutes to reactivate Google Voice again, but once that was done everything seemed to work fine.