I struggled for a long time with getting 500 server errors. First when trying to run gallery/setup/index.php and then with trying to open my galleries.
I traced the problem to the permissions on the gallery & setup & temporary directories.
Setting the permissions on any of these directories to 777 caused the failure apparently. Once all 3 were set to 755, gallery setup and the gallery ran perfectly.
This is on an apache virtual host [Apache/2.0.50 (Fedora) ] with PHP Version 4.3.10