Ubuntu Software Center doesn't lauch/uninstall [12.10]

This cropped up somewhere during the process of installing an nvidia driver (310.32) for my graphic card.
Whenever I clicked on the Ubuntu Software Center icon on the launcher, it seemed to work (animation on icon to show that it was starting), and then nothing.
So I did the first stupid thing, I tried to remove and reinstall the Software Center; apparently, the remove didn't work properly, so I tried again. Here's the terminal session:

parth@Gladoss:~$ sudo apt-get remove software-center
Reading package lists... Done
Building dependency tree       
Reading state information... Done

The following packages will be REMOVED:
  software-center
0 upgraded, 0 newly installed, 1 to remove and 304 not upgraded.
1 not fully installed or removed.
After this operation, 4,485 kB disk space will be freed.
Do you want to continue [Y/n]? Y
(Reading database ... 176079 files and directories currently installed.)
Removing software-center ...
dpkg: error processing software-center (--remove):
 unable to securely remove '/usr/share/app-install/menu.d/featured.menu': Not a directory

No apport report written because MaxReports is reached already
Errors were encountered while processing:
 software-center
E: Sub-process /usr/bin/dpkg returned an error code (1)
parth@Gladoss:~$ 

Let me know how I can properly remove and reinstall the program.
Thanks.

EDIT:
command sudo apt-get update comes to a stop with error message (terminal)

---

W: GPG error: ppa.launchpad.net quantal Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY 4F191A5A8844C542

---

EDIT:

Tried the commands:
(i)sudo rm /usr/share/app-install/menu.d/featured.menu
result : directory does not exist.
(ii)sudo rm -rf /usr/share/app-install/menu.d/featured.menu
result : nothing. Terminal just gets ready to accept new line.
Further, I tried "sudo apt-get install software-center". Same error message as original post.

EDIT:
sudo apt-get --reinstall install software-center returns

---

(Reading database ... 176080 files and directories currently installed.)
Preparing to replace software-center 5.4.1.2 (using .../software-center_5.4.1.4_all.deb) ...
Unpacking replacement software-center ...
dpkg: error processing /var/cache/apt/archives/software-center_5.4.1.4_all.deb (--unpack):
trying to overwrite '/usr/share/app-install/desktop', which is also in package app-install-data-partner 12.12.10
Processing triggers for desktop-file-utils ...
Processing triggers for bamfdaemon ...
Rebuilding /usr/share/applications/bamf.index...

Processing triggers for gnome-menus ...
Processing triggers for hicolor-icon-theme ...
Errors were encountered while processing:
/var/cache/apt/archives/software-center_5.4.1.4_all.deb
E: Sub-process /usr/bin/dpkg returned an error code (1)

---

EDIT :
I figured something was wrong with the dpkg, I googled that.

Some commands I tried afterwards.

---

parth@Gladoss:~$ sudo dpkg --audit
The following packages are only half installed, due to problems during
installation. The installation can probably be completed by retrying it;
the packages can be removed using dselect or dpkg --remove:
software-center Utility for browsing, installing, and removing software

---

---

parth@Gladoss:~$ sudo dpkg --remove software-center
(Reading database ... 176079 files and directories currently installed.)
Removing software-center ...
dpkg: error processing software-center (--remove):
unable to securely remove '/usr/share/app-install/menu.d/featured.menu': Not a directory
Errors were encountered while processing:

software-center

---

[In succession]

EDIT :
sudo dpkg -L software-center
brings up a whole lot of files; including /usr/share/app-install/menu.d/featured.menu
If it's being shown here, how is it that a recursive force remove ignores it? Are their any other commands (not related to rm) which might work?