I've seen a similar problem, but, strangely, it seemed to resolve itself! Possibly - though this is a guess - it may not be launching completely, next time it occurs try closing it and opening something else, then close that and try opening 'Add/Remove software' again. Sorry I can't be more help.
To get the right answer, one must first ask the right question!
Desktop #1 F18
Desktop #2 Mint 14
Laptop: Macpup 529
Netbook: Debian ARM