12.04 - apt-get fails to upgrade packages

I'm running Ubuntu 12.04 Server:

user@host:~$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 12.04.5 LTS
Release:        12.04
Codename:       precise

My issue is this: When I go to upgrade packages (specifically looking for php5, but it happens for many/most/all) this is what I get:

user@host:~$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
You might want to run 'apt-get -f install' to correct these.
The following packages have unmet dependencies:
 apache2-suexec-custom : Depends: apache2-bin but it is not installed
E: Unmet dependencies. Try using -f.
user@host:~$ sudo apt-get -f install
Reading package lists... Done
Building dependency tree
Reading state information... Done
Correcting dependencies... Done
The following packages were automatically installed and are no longer required:
  libnet-xwhois-perl libtommath0
Use 'apt-get autoremove' to remove them.
The following extra packages will be installed:
  apache2-bin
The following NEW packages will be installed:
  apache2-bin
0 upgraded, 1 newly installed, 0 to remove and 29 not upgraded.
1 not fully installed or removed.
Need to get 0 B/953 kB of archives.
After this operation, 3576 kB 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 ... 95668 files and directories currently installed.)
Unpacking apache2-bin (from .../apache2-bin_2.4.16-4+deb.sury.org~precise+4_amd64.deb) ...
dpkg: error processing /var/cache/apt/archives/apache2-bin_2.4.16-4+deb.sury.org~precise+4_amd64.deb (--unpack):
 trying to overwrite '/usr/share/man/man8/apache2.8.gz', which is also in package apache2.2-common 2.2.22-1ubuntu1.10
dpkg-deb (subprocess): subprocess data was killed by signal (Broken pipe)
dpkg-deb: error: subprocess  returned error exit status 2
Processing triggers for man-db ...
Errors were encountered while processing:
 /var/cache/apt/archives/apache2-bin_2.4.16-4+deb.sury.org~precise+4_amd64.deb
E: Sub-process /usr/bin/dpkg returned an error code (1)

What can I do to resolve these errors? I'd really like to get a PHP version newer than 5.3, since I have multiple items that require PHP v5.4 minimum.

NOTE: I am not trying to fix the locale issue, I'm trying to fix the dpkg error. This server has always had a locale issue, and it's completely separate. Sorry, but this ain't no duplicate.

Edits for added code:

user@host:~$ sudo dpkg --configure -a
dpkg: dependency problems prevent configuration of apache2-suexec-custom:
 apache2-suexec-custom depends on apache2-bin; however:
  Package apache2-bin is not installed.
dpkg: error processing apache2-suexec-custom (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 apache2-suexec-custom

Output of sudo apt-get install apache2:

user@host:~$ sudo apt-get install apache2
Reading package lists... Done
Building dependency tree
Reading state information... Done
You might want to run 'apt-get -f install' to correct these:
The following packages have unmet dependencies:
 apache2 : Depends: apache2-bin (= 2.4.16-4+deb.sury.org~precise+4) but it is not going to be installed
           Depends: apache2-data (= 2.4.16-4+deb.sury.org~precise+4) but it is not going to be installed
           Conflicts: apache2.2-bin but 2.2.22-1ubuntu1.10 is to be installed
           Conflicts: apache2.2-common but 2.2.22-1ubuntu1.10 is to be installed
 apache2-suexec-custom : Depends: apache2-bin but it is not going to be installed
E: Unmet dependencies. Try 'apt-get -f install' with no packages (or specify a solution).

OK, so here's what I just discovered. Things seem to work OK with apache2-suexec-custom removed. But I still get this:

user@host:~$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages have been kept back:
  apache2 libapache2-mod-php5 libjson0:i386 php-apc php-pear php5 php5-cgi php5-cli php5-common php5-curl php5-dev php5-fpm php5-gd php5-imagick php5-imap php5-intl
  php5-ldap php5-mcrypt php5-memcache php5-ming php5-mysql php5-ps php5-pspell php5-recode php5-snmp php5-sqlite php5-tidy php5-xmlrpc php5-xsl
0 upgraded, 0 newly installed, 0 to remove and 29 not upgraded.
user@host:~$ sudo apt-get -f install
Reading package lists... Done
Building dependency tree
Reading state information... Done
0 upgraded, 0 newly installed, 0 to remove and 29 not upgraded.

So what's with the 29 not upgraded? I'm going to browse around and look for the answer in other questions in the meantime...

SWEET!!! See DanielSmith-Chatbot's answer for my solution...

OK here's what the issue was:

There was a severely messed up package by the name of apache2-suexec-custom that needed and hated the same package. Remove that, and the other packages are now dist-upgradeable. Run sudo apt-get dist-upgrade ; sudo apt-get upgrade and everything is upgraded.

Thanks for your help(ish) guys! Not an expectedd solution, but it worked!