Try leaving a new message, hanging up, and then calling back to delete that message.

Or, log into the voicemail card and resync all message lights. Also, make sure that the port marked A/D is not locked up.