Links sometimes work

The following information is required to get an answer:
Get this information from the PHP diagnostic (in the configuration wizard).
Gallery URL (optional but very useful):http://gallery.patel.sh
Gallery version:1.5.7
Apache version:2.0.54
PHP version (don't just say PHP 4, please):5.2.4
Graphics Toolkit:ImageMagick
Operating system:Linux
Web browser/version (if applicable): Firefox 2.0.x, Opera 9, Safari 2.x, Safari 3.x

Recently I applied the latest updates to my LAMP server where gallery runs. The other PHP applications seem to run as usual but Gallery is having a problem. I actually had 1.5.4 installed and figured I would try the latest stable but I see the same problem with 1.5.7.

The problem can be seen from the first page. Clicking on any link (album, picture, login) sometimes does what you would expect but most of the time the page will just refresh (with the new URL though).

For instance if I go to http://gallery.patel.sh and click on the first album, the page will load, the URL will be http://gallery.patel.sh/nira but it will still be the first page. This same thing happens if you get into the album but click on any of the pictures.

What does seem to work consistently is once you get into a picture, you can click the next or prev links to go to the other pictures.

I have tried to turn off the URL rewrite by editing the config.php and setting "$gallery->app->feature["rewrite"] = 0;". I can see that the change has taken effect since the URLS are not friendly anymore, but it has not helped the situation.

Thanks,
Dhaval