Unable to create new album and more problems....

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):www.lamayeshe.com/lygallery/Main-Album
Gallery version:1.5.3
Apache version:1.3.27
PHP version (don't just say PHP 4, please):4.2.3
Graphics Toolkit:netpbm
Operating system:linux
Web browser/version (if applicable):

Hi,

We have been using Gallery for past 3-4 months with out much problem.
But today I have encountered following problems:

1. Unable to create new album:
Got msg: "The Album or photo that you were attempting to view either does not
exist, or requires user privileges that you do not possess".

I changed the permission of "albums" folder to 777 then also got same err.
msg.

2. Unable to create "new user". Showed me the msg. that new user created but not able to log in with new user id.

3. While trying to fix these problems, my config.php got totally wiped off. Got following msg: "Gallery has not been configured!"
and now I am not able to edit the config file (ofcourse, I changed the mode to 777).

If all these problems are due to some changes done by my host, then what exactly I need to ask them to change.

Thanks,