Ubuntu Software Center crashes due to error in its Python code

Ubuntu Software Center crashes due to error in its Python code

I searched for that, but did not find any reference to it on this site. If you know some, please refer me to it - the issues I have seen have different symptoms. So, to the point...
I had Ubuntu 12.04 LTS for a long time, switched to Ubuntu Gnome Shell etc. Recently I wanted to move to Ubuntu 13.04 and found an issue that seemingly occurred previously, but at seemingly random rate. Now I cannot start Ubuntu Software Center at all.
When I run the console I see:
$ software-center

(process:22270): Gtk-WARNING **: Locale not supported by C library.
    Using the fallback 'C' locale.
Traceback (most recent call last):
  File "/usr/bin/software-center", line 36, in <module>
    from softwarecenter.utils import (
  File "/usr/share/software-center/softwarecenter/utils.py", line 47, in <module>
    from config import get_config
  File "/usr/share/software-center/softwarecenter/config.py", line 33, in <module>
    class SoftwareCenterConfig(object, SafeConfigParser):
  File "/usr/lib/python2.7/abc.py", line 87, in __new__
    cls = super(ABCMeta, mcls).__new__(mcls, name, bases, namespace)
TypeError: Error when calling the metaclass bases
    Cannot create a consistent method resolution
order (MRO) for bases SafeConfigParser, object
I hoped that following these ideas (source) could be helpful:
$ sudo apt-get purge software-center
$ sudo apt-get update
$ sudo apt-get dist-upgrade
$ sudo apt-get install software-center
$ sudo dpkg-reconfigure software-center --force
It was not:
$ sudo apt-get purge software-center
Reading package lists... Done
Building dependency tree      
Reading state information... Done
The following package was automatically installed and is no longer required:
  software-center-aptdaemon-plugins
Use 'apt-get autoremove' to remove it.
The following packages will be REMOVED:
  software-center*
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
After this operation, 0 B of additional disk space will be used.
Do you want to continue [Y/n]? Y
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LANG = "en_US.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory
(Reading database ... 269627 files and directories currently installed.)
Removing software-center ...
Purging configuration files for software-center ...
rmdir: failed to remove `/var/cache/software-center/xapian/': No such file or directory
dpkg: error processing software-center (--purge):
 subprocess installed post-removal script returned error exit status 1
Errors were encountered while processing:
 software-center
E: Sub-process /usr/bin/dpkg returned an error code (1)
What am I doing wrong? How can I get rid of Ubuntu Software Center causing error and install version that will not have that?
Or maybe the problem is with my Python interpreter?
$ python --version
Python 2.7.3
I believe Ubuntu is gradually m