I just happened to try deploying a Cake app in the same way to a shared server using CPanel and had exactly the same problem. What I discovered is that somehow (I think when I extracted the zip to the public_html directory there was an empty .htaccess file that didn't want to be replaced) the .htaccess file in the root of the application was empty.
Just make sure the .htaccess file in the root of your application (i.e. in public_html) contains this:
<IfModule mod_rewrite.c>
RewriteEngine on
RewriteRule ^$ app/webroot/ [L]
RewriteRule (.*) app/webroot/$1 [L]
</IfModule>
Worked fine for me and I'm all set now!