Ubuntu – How to fix the “Unable to calculate upgrade” issue from command line when upgrading from 12.04 to 14.04

I'm running Ubuntu 12.04 on DigitalOcean server.

I would like to upgrade it to later releases (12.04->14.04->16.04), but fail to do so due to the mentioned mistake.
DigitalOcean provides a tutorial for upgrade, but it is not helpful because it doesn't explain how to solve the issue.
I've also tried all answers in similar questions, that use command line.
The problem is essentially the same as here and here:

"An unresolvable problem occurred while calculating the upgrade: E:Unable to correct problems, you have held broken packages. This can be caused by:
* Upgrading to a pre-release version of Ubuntu
* Running the current pre-release version of Ubuntu
* Unofficial software packages not provided by Ubuntu"

• I have no ppa added
• I didn't add any extra sources to /etc/apt/sources.list. But I must mention that there are listed only DigitalOcean mirrors, no ubuntu default servers.
• I have > 900 packages listed as broken in /var/log/dist-upgrade/apt.log. (It seems like they all are broken)
• I tried these commands (in proper order) apt-get update, apt-get upgrade, apt-get dist-upgrade, apt-get --purge autoremove, apt-get autoclean, apt-get purge $(dpkg -l | awk '/^rc/ { print $2 }'), etc that are listed in answers to similar questions, but they do nothing as they think everything is OK.

Do you have any more suggestions on how to fix the problem?

UPDATE: I thought an issue with DigitalOcean servers in sources.list might be an issue, so I changed them to original Ubuntu ones. Now I get only 2 errors in apt.log:

ERROR getting the encoding failed
Traceback (most recent call last):
  File "/tmp/update-manager-cwZhf2/DistUpgrade/DistUpgradeView.py", line 40, in <module>
    locale.setlocale(locale.LC_ALL, "")
  File "/usr/lib/python2.7/locale.py", line 539, in setlocale
    return _setlocale(category, locale)
Error: unsupported locale setting
ERROR Dist-upgrade failed: 'E:Unable to correct problems, you have held broken packages.

I don't know if locale error causes it. I tried to fix it by exporting LANG, LANGUAGE and LC_ALL to "en_US.utf8", but didn't help. I will try to fix it and update the question if it helps.

UPDATE 2:
Output of locale command:

$locale
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
LANG=en_US.UTF-8
LANGUAGE=en_US.UTF-8
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=en_US.UTF-8

UPDATE 3:
After setting locale to "C" (thanks to Gunnar Hjalmarsson), the locale error is gone from apt.log, but invoking do-release-upgrade still the leads to error:

DEBUG /openCache(), new cache size 47033
DEBUG need_server_mode(): can not find a desktop meta package or key deps, running in server mode
DEBUG Installing 'locales' (priority in required set 'required' but not scheduled for install)
ERROR Dist-upgrade failed: 'E:Unable to correct problems, you have held broken packages.'

and still no upgrade.