Howdy,
What php handler are you using? It's likely suphp, and if that case try 644 then 755. If the php processes are running as user's not apache or nobody that should be more than enough. Anything that *needs* 777 that isn't /tmp is going to lead to tears.
Thanks!