Thought I’d see if you solved this. I am getting the same issue.
I’ve wordpress 3.41 and I’m hosting with 1&1 on a shared server.
I can’t even upload really small images.
This is the message I get when trying to upload a 21KB JPG image.
Fatal error: Out of memory (allocated 29884416) (tried to allocate 850 bytes) in /homepages/…/htdocs/word/wp-includes/media.php on line 258
I’ve also tried using NextGen gallery and it fails when uploading images or even importing a folder that already has images inside it (this might be unrelated – I’m not sure)