yeah, I am pretty sure your server doesn't have suPHP installed. Then you need to chmod that to 777, and change it back to 755 again after you installed.
yes.. 777 is a security risk but some hostings need folder permissions to be chmod to 777 for them to appear as writable.. what's your hosting? how about asking them to install suphp (if you use VPS or dedicated server)
or if you are trying to install Joomla 1.5, hey, it has ftp layer, and it can works without needing to chmod to 777 and I think it can write the files. Let's try