My Ubuntu 14.04 setup seems to be hopelessly fouled up, to the extent that I can no longer successfully install any packages using apt-get install. The common error is "no module named debian.deb822". An example is below. Note that my goal is not necessarily to install this particular package; just to be able to install any packages. Any help would be greatly appreciated!

box:~/python> sudo apt-get install update-notifier

Reading package lists... Done

Building dependency tree       

Reading state information... Done

apturl is already the newest version.

apturl-common is already the newest version.

0 upgraded, 0 newly installed, 0 to remove and 394 not upgraded.

5 not fully installed or removed.

After this operation, 0 B of additional disk space will be used.

Do you want to continue? [Y/n] Y

Setting up update-notifier-common (0.154.1ubuntu1) ...

Traceback (most recent call last):

  File "/usr/lib/update-notifier/package-data-downloader", line 26, in <module>

    import debian.deb822

ImportError: No module named debian.deb822

dpkg: error processing package update-notifier-common (--configure):

 subprocess installed post-installation script returned error exit status 1

dpkg: dependency problems prevent configuration of update-notifier:

 update-notifier depends on update-notifier-common (= 0.154.1ubuntu1); however:

  Package update-notifier-common is not configured yet.



dpkg: error processing package update-notifier (--configure):

 dependency problems - leaving unconfigured

dpkg: dependency problems prevent configuration of update-manager:

 update-manager depends on update-notifier; however:

  Package update-notifier is not configured yet.



dpkg: error processing package update-manager (--configure):

 dependency problems - leaving unconfigured

dpkg: dependency problems prevent configuration of ubuntu-release-upgrader-gtk:

 ubuntu-release-upgrader-gtk depends on update-manager; however:

  Package update-manager is not configured yet.



dpkg: error processing package ubuntu-release-upgrader-gtk (--configure):

 dependency problems - leaving unconfigured

dpkg: dependency problems prevent configuration of ubuntu-desktop:

 ubuntu-desktop depends on ubuntu-releasNo apport report written because the error message indicates its a followup error from a previous failure.

                                                                  No apport report written because the error message indicates its a followup error from a previous failure.

            No apport report written because MaxReports is reached already

                                                                          No apport report written because MaxReports is reached already

                                                        e-upgrader-gtk; however:

  Package ubuntu-release-upgrader-gtk is not configured yet.

 ubuntu-desktop depends on update-manager; however:

  Package update-manager is not configured yet.

 ubuntu-desktop depends on update-notifier; however:

  Package update-notifier is not configured yet.



dpkg: error processing package ubuntu-desktop (--configure):

 dependency problems - leaving unconfigured

Errors were encountered while processing:

 update-notifier-common

 update-notifier

 update-manager

 ubuntu-release-upgrader-gtk

 ubuntu-desktop

E: Sub-process /usr/bin/dpkg returned an error code (1)

EDIT 1:
After running "sudo apt-get update" and "sudo apt-get upgrade," the output is slightly different but the same error is thrown:

box:~> sudo apt-get upgrade update-notifier

Reading package lists... Done

Building dependency tree       

Reading state information... Done

Calculating upgrade... Done

update-notifier is already the newest version.

The following packages have been kept back:

  libreoffice libreoffice-base libreoffice-base-core libreoffice-base-drivers

  libreoffice-calc libreoffice-common libreoffice-core libreoffice-draw

  libreoffice-gnome libreoffice-gtk libreoffice-gtk3 libreoffice-help-en-us

  libreoffice-impress libreoffice-math libreoffice-style-galaxy

  libreoffice-style-human libreoffice-style-tango libreoffice-writer

  linux-generic linux-generic-lts-vivid linux-headers-generic

  linux-headers-generic-lts-vivid linux-image-generic

  linux-image-generic-lts-vivid linux-signed-generic-lts-vivid

  linux-signed-image-generic-lts-vivid linux-tools-virtual-lts-wily

  openjdk-8-jdk openjdk-8-jre openjdk-8-jre-headless python3-uno shim-signed

0 upgraded, 0 newly installed, 0 to remove and 32 not upgraded.

5 not fully installed or removed.

After this operation, 0 B of additional disk space will be used.

Do you want to continue? [Y/n] Y

Setting up update-notifier-common (0.154.1ubuntu1) ...

Traceback (most recent call last):

  File "/usr/lib/update-notifier/package-data-downloader", line 26, in <module>

    import debian.deb822

ImportError: No module named debian.deb822

dpkg: error processing package update-notifier-common (--configure):

 subprocess installed post-installation script returned error exit status 1

dpkg: dependency problems prevent configuration of update-notifier:

 update-notifier depends on update-notifier-common (= 0.154.1ubuntu1); however:

  Package update-notifier-common is not configured yet.



dpkg: error processing package update-notifier (--configure):

 dependency problems - leaving unconfigured

dpkg: dependency problems prevent configuration of update-manager:

 update-manager depends on update-notifier; however:

  Package update-notifier is not configured yet.



dpkg: error processing package update-manager (--configure):

 dependency problems - leaving unconfigured

dpkg: dependency problems prevent configuration of ubuntu-release-upgrader-gtk:

 ubuntu-release-upgrader-gtk depends on update-manager; however:

  Package update-manager is not configured yet.



dpkg: error processing package ubuntu-release-upgrader-gtk (--configure):

 dependency problems - leaving unconfigured

dpkg: dependency problems prevent configuration of ubuntu-desktop:

 ubuntu-desktop depends on ubuntu-releasNo apport report written because the error message indicates its a followup error from a previous failure.

                                                                  No apport report written because the error message indicates its a followup error from a previous failure.

            No apport report written because MaxReports is reached already

                                                                          No apport report written because MaxReports is reached already

                                                        e-upgrader-gtk; however:

  Package ubuntu-release-upgrader-gtk is not configured yet.

 ubuntu-desktop depends on update-manager; however:

  Package update-manager is not configured yet.

 ubuntu-desktop depends on update-notifier; however:

  Package update-notifier is not configured yet.



dpkg: error processing package ubuntu-desktop (--configure):

 dependency problems - leaving unconfigured

E: Sub-process /usr/bin/dpkg returned an error code (1)

EDIT 2: After running @Raphael 's suggested fixes the output has changed somewhat, but the problem persists:

box:~/Downloads> sudo apt-get install update-notifier

Reading package lists... Done

Building dependency tree       

Reading state information... Done

update-notifier is already the newest version.

The following packages were automatically installed and are no longer required:

  libreoffice-gtk3 linux-headers-3.13.0-77 linux-headers-3.13.0-77-generic

  linux-image-3.13.0-77-generic linux-image-extra-3.13.0-77-generic

  linux-lts-wily-tools-4.2.0-27 linux-tools-4.2.0-27-generic

Use 'apt-get autoremove' to remove them.

0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.

5 not fully installed or removed.

After this operation, 0 B of additional disk space will be used.

Do you want to continue? [Y/n] Y

Setting up update-notifier-common (0.154.1ubuntu1) ...

Traceback (most recent call last):

  File "/usr/lib/update-notifier/package-data-downloader", line 26, in <module>

    import debian.deb822

ImportError: No module named debian.deb822

dpkg: error processing package update-notifier-common (--configure):

 subprocess installed post-installation script returned error exit status 1

dpkg: dependency problems prevent configuration of update-notifier:

 update-notifier depends on update-notifier-common (= 0.154.1ubuntu1); however:

  Package update-notifier-common is not configured yet.



dpkg: error processing package update-notifier (--configure):

 dependency problems - leaving unconfigured

dpkg: dependency problems prevent configuration of update-manager:

 update-manager depends on update-notifier; however:

  Package update-notifier is not configured yet.



dpkg: error processing package update-manager (--configure):

 dependency problems - leaving unconfigured

dpkg: dependency problems prevent configuration of ubuntu-release-upgrader-gtk:

 ubuntu-release-upgrader-gtk depends on update-manager; however:

  Package update-manager is not configured yet.



dpkg: error processing package ubuntu-release-upgrader-gtk (--configure):

 dependency problems - leaving unconfigured

dpkg: dependency problems prevent configuration of ubuntu-desktop:

 ubuntu-desktop depends on ubuntu-releasNo apport report written because the error message indicates its a followup error from a previous failure.

                                                                  No apport report written because the error message indicates its a followup error from a previous failure.

            No apport report written because MaxReports is reached already

                                                                          No apport report written because MaxReports is reached already

                                                        e-upgrader-gtk; however:

  Package ubuntu-release-upgrader-gtk is not configured yet.

 ubuntu-desktop depends on update-manager; however:

  Package update-manager is not configured yet.

 ubuntu-desktop depends on update-notifier; however:

  Package update-notifier is not configured yet.



dpkg: error processing package ubuntu-desktop (--configure):

 dependency problems - leaving unconfigured

Errors were encountered while processing:

 update-notifier-common

 update-notifier

 update-manager

 ubuntu-release-upgrader-gtk

 ubuntu-desktop

E: Sub-process /usr/bin/dpkg returned an error code (1)