I was experiencing the same issue when setting up on a RHEL (RHEL 5.5 w/ MySQL 5.1.48 & php 5.3.2). Everything worked perfect on my local install (Mac OS X 10.6 w/ MySQL 5.1.47 & php 5.3.1). What solved it for me was to go to command line mysql, log in and grant all to the db using a hostname of '%'.

For example:
mysql> grant all on zenphoto.* to 'admin'@'%';

Obviously, you'll need to change the name of the database and the user associated with your setup.