Found the problem in the PHP configuration (/etc/php.ini) had an error.
The setting "upload_max_filesize" was set to "64MB" which translated to '64 bytes'. (Makes sense right?) The proper configuration is 'upload_max_filesize = 64M'.
This is why the smallest files I used for testing worked but the larger ones failed even when they were under the set limits of a given gallery.
Anyhow, thanks for looking looking into this for me KW802 and big thanks to BJ at Rackspace.com Managed Hosting
for finding the typo and getting it fixed. Sure, it's what they get paid for but these guys are awesome!