I've just installed Plogger for the first time and was able to log into admin and create some collections and albums. When I go to the main gallery page it looks fine and creates some thumbnails from the images I gave it. However, as soon as you click on any of the collections it tries to looks for folders that don't exist.
Turn off cruft-free URLs. It uses mod_rewrite, which is an Apache module. Evidently you're using Apache/1.3.33, but the module is clearly either not enabled or not working as it should.
See, if you go here (http://gallery.michael-newman.com/index.php?level=album&id=2), a non-cruft-free URL, it works fine.
I have the same trouble, if it makes you feel better, but haven't yet gotten help. :)
In the interim, turn off cruft-free and everything will otherwise work fine.