Ubuntu – Can’t get anything to install, dependency errors

I'm extremely new to Linux/command line stuff, so please forgive my ignorance.

Every time I try to install anything using sudo apt-get install ... I get dependency errors.
I'm trying to get OpenSSH Server and GitLab installed on my machine, and whenever I type in the commands, I seem to get a dependency error like so:

sudo apt-get install openssh-server
reading package lists... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 openssh-server : Depends: libwrap0 (>= 7.6-4~) but it is not installable
                  Recommends: ssh-import-id but it is not installable
E: Unable to correct problems, you have held broken packages.

I get similar errors seemingly no matter what I try to install. For example, with sudo apt-get install git, the error changes to:

The following packages have unmet dependencies:
 git : Depends: liberror-perl but it is not installable
E: Unable to correct problems, you have held broken packages

I'm running Ubuntu Server 12.04 LTS x86. I've tried doing sudo apt-get clean, sudo apt-get autoclean, sudo apt-get update, and sevveral other similar things. I've tried rebooting, hell, I even wiped out the server and started from scratch with the same issue. I'm sure I'm doing something obviously wrong, but I just can't seem to track it down. If anyone could help, that'd be fantastic.

Update: I did get OpenSSH working by clean installing the server and selecting OpenSSH during set up.

I found this wiki on apt-get so I tried doing sudo apt-get build-dep git and got the error:

E: Build-Depends-Indep dependency for git cannot be satisfied because package asciidoc has no candidate version

I don't know if that helps determine what's happening.