All my problems were caused by a corrupted update of pygtk2.
I added a new repository for apt-get yesterday and like almost every day I ran an "Upgrade all".
It upgraded pygtk2 and caused a bunch of problems I didn't notice right away, because it's mainly stuff you don't use every day.
I noticed something was wrong when trying to acces my Hardware Browser and it wouldn't run!
I removed pygtk2
#apt-get remove pygtk2
It uninstalled a ton of files, and when finished I selected them all for install from within Synaptic, but this time from the freshrpms repository and everything is back to normal.
A big thank you again to void main from MES if he happens to read this
Also thank you to rnturn for helping pointing out the problem with rpm -Va.
/me is happy again