I had a similar experience when I switched AT&T phones to Samsung Note 2 and wanted to use Google Voicemail. The Notification Bar Voicemail Icon would not clear as I had left a message in the AT&T Voicemail and switched as shown below. This worked for me:
Next time I will make sure my Carrier Voicemail is clear first.
To set up voicemail for Google Voice:
On Phone:
Clicked the Phone Icon
Settings Icon
Call Settings
Voicemail Settings
Changed AT&T number (wrote it down as different from cell phone) to Google Voice Number
Changed Voicemail Service to Google Voice.
In Browser
www.google.com/voice website for my Google Voice Account/Settings
Clicked Edit on my cell number (it was there as this is a new phone/same cell number)
Advanced settings section and on Forwarding Options clicked Activate with Go Straight to Voice Mail
Google Voice provided a long string code/number to enter on cell phone and that worked.
As I said at the top, I got it to work the first time, but had left an old message and had to reset the voicemail to AT&T, listen to voicemails and delete them, then reset to Google Voice. Won't make that mistake again.