I've heard occasional reports about this problem. Unfortunately, I don't know the answer.
Perhaps the "notification database" is corrupted?
You may want to try a few Google searches to see if anyone has figured out how to fix it. Worst-case scenario would be to back up the device and to hard reset it.
Good luck.
--janak