knotify is part of another package. In the software installer in Search check the item ‘RPM provides’ when performing a search and it will tell you in which package it is. I think it’s in kdebase4 packages, which you cannot remove.
I see you’re still running the 4.1.3 version of KDE4. Upgrading to KDE4 4.2.4 would solve this matter AFAIK