I had the same problem on Voda. My solution was to change the notification method in the voicemail setup (ring 121, or your network's equivalent). "Icon Notification" doesn't seem to work on the N900 so I switched to "Message Notification" and now get a text and a blue flashing LED with each voicemail message.