I just created an Ubuntu 16.04 droplet to test this out but I was not able to duplicate the problem. After doing the sudo apt-get update, I ran sudo apt-get install phpmyadmin php-mbstring php-gettext and had the following output:

sudo apt-get install phpmyadmin php-mbstring php-gettext
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following additional packages will be installed:
  apache2 apache2-bin apache2-data apache2-utils dbconfig-common
  dbconfig-mysql fontconfig-config fonts-dejavu-core javascript-common
  libaio1 libapache2-mod-php libapache2-mod-php7.0 libapr1 libaprutil1
  libaprutil1-dbd-sqlite3 libaprutil1-ldap libfontconfig1 libgd3 libjbig0
  libjpeg-turbo8 libjpeg8 libjs-jquery libjs-sphinxdoc libjs-underscore
  liblua5.1-0 libmcrypt4 libtiff5 libvpx3 libxpm4 libxslt1.1 mysql-client
  mysql-client-5.7 mysql-client-core-5.7 mysql-common php-cli php-common
  php-gd php-mcrypt php-mysql php-pear php-phpseclib php-tcpdf php-xml
  php7.0-cli php7.0-common php7.0-gd php7.0-json php7.0-mbstring
  php7.0-mcrypt php7.0-mysql php7.0-opcache php7.0-readline php7.0-xml
  ssl-cert
Suggested packages:
  www-browser apache2-doc apache2-suexec-pristine | apache2-suexec-custom
  mysql-server | mariadb-server libgd-tools libmcrypt-dev mcrypt
  php-libsodium php-gmp php-imagick mysql-server | mariadb-server
  | virtual-mysql-server openssl-blacklist
The following NEW packages will be installed:
  apache2 apache2-bin apache2-data apache2-utils dbconfig-common
  dbconfig-mysql fontconfig-config fonts-dejavu-core javascript-common
  libaio1 libapache2-mod-php libapache2-mod-php7.0 libapr1 libaprutil1
  libaprutil1-dbd-sqlite3 libaprutil1-ldap libfontconfig1 libgd3 libjbig0
  libjpeg-turbo8 libjpeg8 libjs-jquery libjs-sphinxdoc libjs-underscore
  liblua5.1-0 libmcrypt4 libtiff5 libvpx3 libxpm4 libxslt1.1 mysql-client
  mysql-client-5.7 mysql-client-core-5.7 mysql-common php-cli php-common
  php-gd php-gettext php-mbstring php-mcrypt php-mysql php-pear php-phpseclib
  php-tcpdf php-xml php7.0-cli php7.0-common php7.0-gd php7.0-json
  php7.0-mbstring php7.0-mcrypt php7.0-mysql php7.0-opcache php7.0-readline
  php7.0-xml phpmyadmin ssl-cert
0 upgraded, 57 newly installed, 0 to remove and 30 not upgraded.
Need to get 29.4 MB of archives.
After this operation, 148 MB of additional disk space will be used.
Do you want to continue? [Y/n] 

Make sure you ran the apt-get update command first so that your local package lists are up to date and that you are following this tutorial on a droplet running Ubuntu 16.04.

Also I'm having this error any ideas?

I think this problem only occurs at NYC servers

I have tried with unutu 16.10 at ams and nyc datacenters. ams is ok nyc seems using diffrent ubuntu image.
I hope they fix this soon.
You may play with source.list to add ubuntu universe servers or add a droplet at ams than move it to elsewhere may work for quick.

is there a fix for this ???? !!!