Are you resizing the image while uploading? The image resize process takes up a lot of memory. Usually the only solution is to up the available memory_limit value in the php.ini file. You can sometimes fix it on the top of the page with php on the top of the page as well like:
<?php
ini_set('memory_limit', '1024M');
?>
That would be more than enough, but there may be limits or you may not be able to change it at all on a shared server.