Just a few things I can think of off the top of my head. Run a php info script in the locate where you plan to install expressionengine. See what the script tells you the memory limit is there at that point. It is possible there may be some configuration override happening that means what you've got in cpanel is not what you actually have where you are trying to install.
Another thing that I'm sure you probably know, but I have seen people make the mistake before:
PHP memory limit is different from PHP upload size.
If it is allowed on the server you are working with you could try the following in an .htaccess file to get the settings how you want them:
php_value memory_limit 32M