I have just downloaded and installed Phoca Guestbook and I ran into the same 404 error trap. But there is a simple solution.
I did the following:
1. Install Phoca Guestbook

2. In the backend create a new guestbook, there isn't any yet!
3. create a menu entry, anywhere you like and configure this entry.
YOU MUST SELECT A PREVIOUSLY CREATED GUESTBOOK:

Hope it works for you too
