Assuming that you are running 4.5, the following bug might be the reason https://core.trac.wordpress.org/ticket/36534. (In short, the more aggressive image compression introduced in 4.5 causes imagemagick to fail).
There are some suggested solutions in the ticket, but it also sounds like increasing the max memory might help.