Maybe the “memory_limit”, “post_max_size” and “upload_max_filesize” on that shared server is very limited? Try contacting your host and ask them to increase those limits, just to see if it gets that working.
I had that same problem on two different servers and manually changed the php.ini configuration file, confirming the solution.
See also:
http://forum.getkirby.com/t/the-upload-failed-when-uploading-files/1413