We're running version 7.34 on a GoDaddy CentOS VPS, sans CPANEL (in other words no support other than just connectivity).

Every time I try to manually run the check updates for module updates I get this:

Checking available update data

Error checking available update data.
Please continue to the error page
An AJAX HTTP request terminated abnormally. Debugging information follows. Path: /batch?id=323&op=do StatusText: error ResponseText: ReadyState: 0

We've disabled the Admin menu bar as I heard that could contribute to the latency.

Running 'drush up any_module' (from CLI) takes at least 10 minutes to run.

/var/log/messages has no recent messages

dblog only has some page not found and login messages.

In Status Report there's this:

Warning
Drupal core update status No available releases found
There was a problem checking available updates for Drupal. See the available updates page for more information and to install your missing updates.

/var/log/php-errors.log is blank.

It's 12:12 PM EST as I'm writing this and these are the last logs in the HTTP Apache

[Fri Feb 27 07:28:46 2015] [error] [client 176.96.154.154] client sent HTTP/1.1 request without hostname (see RFC2616 section 14.23): /tmUnblock.cgi
[Fri Feb 27 08:55:15 2015] [error] [client 71.253.124.116] client sent HTTP/1.1 request without hostname (see RFC2616 section 14.23): /tmUnblock.cgi
[Fri Feb 27 09:11:34 2015] [error] [client 46.4.82.204] script not found or unable to stat: /var/www/cgi-bin/php

top - 12:15:53 up 9 days, 21:58, 2 users, load average: 1.08, 1.03, 1.00
Tasks: 33 total, 1 running, 32 sleeping, 0 stopped, 0 zombie
Cpu(s): 0.0%us, 0.0%sy, 0.0%ni,100.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st
Mem: 2097152k total, 947492k used, 1149660k free, 0k buffers
Swap: 0k total, 0k used, 0k free, 0k cached

What else can I check?

Edit:
This just happened:

Error message
PDOException: SQLSTATE[HY000]: General error: 1205 Lock wait timeout exceeded; try restarting transaction: DELETE FROM {cache} WHERE (cid LIKE :db_condition_placeholder_0 ESCAPE '\\') ; Array ( [:db_condition_placeholder_0] => ctools\_plugin\_files:% ) in cache_clear_all() (line 167 ofl/includes/cache.inc).
The website encountered an unexpected error. Please try again later.