Success! I tried almost all of the solutions (including recreating the upgrade folder and changing permissions) but none of them worked.
The solution that worked for me was to change from PureFTP to ProFTP inside of the Web Host Manager (root) interface. This can be changed in WHM Main >> Service Configuration >> FTP Server Selection.
If you are on a shared server and do not have access to WHM, try contacting your hosting company. I also have a WordPress install on a shared server for another site I run, but the auto update worked fine there. I was having problems on my own server at a different hosting company.
