If you are having issues with voicemail message notifications while running on Android 2.3 (commonly known as Gingerbread), upgrade with the most recent version of the operating system using the native settings menu on your mobile device.
If no update is available, make sure you are in good data coverage, and power off your device before attempting another update.