I'm using Chrome with HTTPS Everywhere installed.
Enabling the experimental rule for MusicBrainz under HTTPS Everywhere now allows my covers to load.

Note that according to Chrome developers tools, the error I was getting was:

XMLHttpRequest cannot load http://mbid-e9923506-6ac2-4293-b887-dfdb0876fb0d.s3.us.archive.org/ . Response for preflight is invalid (redirect)

Going to that URL shows...

This XML file does not appear to have any style information associated with it. The document tree is shown below.
<Error>
<Code>NoSuchBucket</Code>
<Message>The specified bucket does not exist.</Message>
<Resource>
mbid-e9923506-6ac2-4293-b887-dfdb0876fb0d not found by Metadata::get_obj()[server]
</Resource>
<RequestId>c86c4406-35af-4c76-8b94-39ddd4883b29</RequestId>
</Error>

Is it possible there is a race (or lack of co-ordination) between the http and https servers when uploading a cover?

This problem is still prevalent and persistent for me.
I'm building a list with all my failures on them - http://musicbrainz.org/collection/ec91b64e-8da7-42c2-b161-41c7f0a686e9
Size and format of the file seems irrelevant.
Most scans are mine, but one from bandcamp also fails.

This ticket is currently conflating a lot of different issues, so I opened MBS-8543 to target the specific MalformedPOSTRequest error given in the last comment.

This is the response from the webserver after receiving an "Error uploading image". Taken from Opera's network monitor.

General:
Remote Address:207.241.224.50:80
Request URL:http://mbid-85dfbc75-c389-4c36-a0f2-4d7b41723478.s3.us.archive.org/
Request Method:POST
Status Code:400 Bad Request

Request headers:
Accept:/
Accept-Encoding:gzip, deflate, lzma
Accept-Language:en-US,en;q=0.8
Connection:keep-alive
Content-Length:118375
Content-Type:multipart/form-data; boundary=----WebKitFormBoundaryIsYhPL3Udo1HvFke
DNT:1
Host:mbid-85dfbc75-c389-4c36-a0f2-4d7b41723478.s3.us.archive.org
Origin:http://musicbrainz.org
Referer:http://musicbrainz.org/release/85dfbc75-c389-4c36-a0f2-4d7b41723478/add-cover-art
User-Agent:Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/44.0.2403.155 Safari/537.36 OPR/31.0.1889.174

Response:
<?xml version='1.0' encoding='UTF-8'?>
<Error><Code>MalformedPOSTRequest</Code><Message>The body of your POST request is not well-formed multipart/form-data.</Message><Resource>signature 'jUnZxoP/XdnM4OR0j2ODWdKIYxk=' doesn't match computed: 'IJWx1j3lvkS9Wmicvuh5O1Sjq74=' for this policy</Resource><RequestId>b68b06cc-f95e-4654-bdf1-2029c55983ee</RequestId></Error>

I get this error over and over and it is very annoying.
The "Error uploading image" will appear each time after the "Uploading Image ..." and not reaching the point of "Creating edit ..."
Is there nobody who can resolve this issue?

I get this error more often than not, with all kinds of images. Both large (e.g. 4 MB) and small (e.g. 300 KB) images . I think only one in about 4 uploads finishes ok, others return this error. When I retry a couple of times it eventually succeeds. I have been able to submit all images eventually after trying a couple of times. (So it's not something that is consistent with a certain image).

I'm using Firefox (current version 40.0.3 but also had it with older versions) on Windows 7. I'm behind a NAT router but no additional outgoing firewall or anything.

I ran into the same problem trying to upload this image to this page.

Error in the console: XMLHttpRequest cannot load http://mbid-e6299b97-4d60-47a6-8ad4-23408f4c1a04.s3.us.archive.org/. The request was redirected to 'https://mbid-e6299b97-4d60-47a6-8ad4-23408f4c1a04.s3.us.archive.org/', which is disallowed for cross-origin requests that require preflight.

Request info:
General:
Request URL:http://mbid-e6299b97-4d60-47a6-8ad4-23408f4c1a04.s3.us.archive.org/
Request Method:OPTIONS
Status Code:307 Internal Redirect
Response Headers:
Access-Control-Allow-Credentials:true
Access-Control-Allow-Origin:http://musicbrainz.org
Location:https://mbid-e6299b97-4d60-47a6-8ad4-23408f4c1a04.s3.us.archive.org/
Non-Authoritative-Reason:Delegate
Request Headers:
Provisional headers are shown
Access-Control-Request-Headers:content-type
Access-Control-Request-Method:POST
Origin:http://musicbrainz.org
Referer:http://musicbrainz.org/release/e6299b97-4d60-47a6-8ad4-23408f4c1a04/add-cover-art
User-Agent:Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/41.0.2272.76 Chrome/41.0.2272.76 Safari/537.36

I run into the same issue again and again:
http://forums.musicbrainz.org/viewtopic.php?id=5902

@nikki: How exactly can I check "the network requests in the browsers' developers tools"?

I just saw something which is presumably the same. When checking the network requests in the browser's developer tools it was returning:

HTTP/1.0 503 Service Unavailable
Cache-Control: no-cache
Content-Type: text/html

<html><body><h1>503 Service Unavailable</h1>
No server is available to handle this request.
</body></html>

There's not really much we can do about that...

I've encountered this bug myself. I don't know what causes it and can't think of many conditions under which it might occur; the last time I saw it was when I was trying to upload a batch of large, high-resolution image files.