Comment 4 for bug 518263

Here is the solution:
1. Backup your /var/lib/dpkg/status file NB You MUST do this first, because if you lose this file, your system is hosed.
In a terminal, run: sudo cp /var/lib/dpkg/status /var/lib/dpkg/status.backup

2. In a terminal, type in the following command: sudo nano /var/lib/dpkg/status
Replace "nano" with gedit, kate or whatever other editor you use.

3. Search for "flashplugin-nonfree" in the opened file.
In nano you can press Ctrl-W, then type "flashplugin-nonfree" (without the quotes) and press Enter
The different entries are delimited by empty lines. This means everything within the block containing
Do not delete the first and best match you get. Keep searching (press Crtl-W, then Enter again in nano) until you find a block (content between two empty lines) starting with:
Package: flashplugin-nonfree

4. Delete this block.
In nano, you can press Crtl-K to delete single lines until the next package appears (you will recognize this by the empty line and another "Package: something" line)

5. Save the file
In nano, Ctrl-X, Y, Enter

5.1 Run this:
sudo apt-get install flashplugin-nonfree
(not needed to get a working system, but wanted to keep the package installed)

5.2 In my case, as I started out doing a dist-upgrade, I ran the following commands:
sudo apt-get -f install
sudo apt-get autoremove
sudo aptitude dist-upgrade

6. restart the system (sudo shutdown -r now).

Source:
https://bugs.launchpad.net/ubuntu/+source/flashplugin-nonfree/+bug/365392