[WordPress 3.8] Upload Media HTTP Error and Internal Server Error

When trying to upload media, we go two different errors.

When using Multiple Uploader, we get an HTTP Error.

When using Single Uploader, we get:

Internal Server Error

The server encountered an internal error or misconfiguration and was unable to complete your request.

Please contact the server administrator, [email protected] and inform them of the time the error occurred, and anything you might have done that may have caused the error.

More information about this error may be available in the server error log.

Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.

This is using WordPress 3.8, PHP 5.4.23, MySQL 5.5 hosted on a VPS with InmotionHosting.

I’ve tried changing the upload path and changing things with .htaccess, but no luck so far. Planned on trying changing permissions, but that’s not a long-term fix. Also disabling all our plugins, but I can today because we have a lot of people training with WordPress. Any suggestions?

EDIT: Just tried changing folder permissions to 777. No go.