Comment 8 for bug 591129

I had this problem. Upon suggestion on irc i tried sudo apt-get -f install and it seemed to clear things up. It not only affected software center but also synaptic, upgrade center and apt-get in terminal.