Ubuntu Software center has issues removing software

When trying to uninstall various things via the Ubuntu Software Center, it will continue to display as if the item is still installed. Clicking to remove the package again results in a generic "Ubuntu Software Center has encountered an error" error message.
Happened on Xubuntu 15.04
With Software Center version: 13.10ubuntu6

ProblemType: Bug
DistroRelease: Ubuntu 15.04
Package: software-center 13.10-0ubuntu6
ProcVersionSignature: Ubuntu 3.19.0-18.18-generic 3.19.6
Uname: Linux 3.19.0-18-generic x86_64
ApportVersion: 2.17.2-0ubuntu1.1
Architecture: amd64
CurrentDesktop: XFCE
Date: Fri May 29 13:17:51 2015
ExecutablePath: /usr/share/software-center/software-center
InstallationDate: Installed on 2015-05-29 (0 days ago)
InstallationMedia: Xubuntu 15.04 "Vivid Vervet" - Release amd64 (20150422.1)
InterpreterPath: /usr/bin/python2.7
PackageArchitecture: all
ProcEnviron:
 LANGUAGE=en_US
 PATH=(custom, no user)
 XDG_RUNTIME_DIR=<set>
 LANG=en_US.UTF-8
 SHELL=/bin/bash
SourcePackage: software-center
UpgradeStatus: No upgrade log present (probably fresh install)