I found in my case, my host instituted Apache mod_security for user protection. After contacting them regarding this issue, they entered an exception for this app and it works as designed.
To whomever reads this, I hope it helps!
-Chris
i have the same issue – ‘upload failed’ – regardless of image size, host or permissions to folders.
WordPress 3.4 installation is successful uploading to media, gallery 3.4 plugin upload using the same image fails.
-Chris