When uploading large-ish res images – Fatal error: Out of memory

When I try to upload images of reasonably high-resolution (1200×1900, for example) I get the following error:

Fatal error: Out of memory (allocated 38010880) (tried to allocate 5184 bytes) in sitename.com/wp-includes/media.php on line 258

Been searching the forums for fixes, many of which suggest modifying the memory_limit parameter in php.ini. However, after contacting my host to change it and then bringing up phpinfo for my site(s), I see the following limits:

memory_limit – 128M
post_max_size – 40M
upload_max_filesize – 64M

These parameters seem like they’d be plenty sufficient, or am I wrong there? I should note that the actual *filesize* of the image doesn’t seem to have a bearing on the Out Of Memory error – the resolution triggers it. A 1200×1900 jpg at a very reasonable 166kb will get the error, a 800×600 of 500kb will not.

Is there another setting I’m missing that’ll avoid this error? Looks like a common problem, but going from past threads on the subject it’s rare that anyone gets a successful fix…

Any help would be much appreciated!