Help a Lost Sheep With Short URLs

So, I'm trying to enable short URLs to make my gallery Google-friendly and I'm having some problems.

When I try the "test url" link in the Site Admin, I get "No input file specified." Actually turning on short URLs gets me the same thing when I try to open an album (the thumbnail for which never showed up, as well).

I suspect it has to do with my host running PHP as CGI. (Incidentally, they're running Apache 1.3.31.)

I attempted to use the URL Rewrite module (0.1.1) from this thread, but that didn't help. FYI, here's how it went:

1. I unpacked the module in the modules directory.
2. I went to Site Admin > Modules and installed URL Rewrite.
3. I clicked "configure."
4. Under "Configuring your Webserver," I get "Apache mod_rewrite is working, but Apache is not configured with the AcceptPathInfo directive enabled." (I was under the impression from the information under the short-URL option in the Site Admin that AcceptPathInfo was only necessary with Apache 2. But, honestly, I don't really understand it, anyway.)
5. Under "Gallery .htaccess file," I get "The .htaccess file does not exist."
6. I create an empty .htaccess file in the gallery2 directory.
7. I click "Test .htaccess Again" and I get "Your .htaccess file is ready to be updated."
8. I click "Update .htaccess" and get "Your .htaccess file is up to date. No changes are required." (The error under "Configuring your Webserver" is still there.]
9. I return to Modules and activate URL Rewrite.
10. The page refreshes with URL Rewrite activated. However, all the styles are gone.
11. I return to the main gallery and I'm suddenly logged out, though everything seems to work OK.
12. I log back in, return to Site Admin > General and turn on short URLs. Everything acts the way it did the first time I turned them on. The styles are also still missing.
13. I turn off short URLs and I deactivate and uninstall URL Rewrite. The .htaccess file remains, so I have to delete it manually.
14. The styles don't return until I truncate the address back to the root (mydomain.com/gallery2/).

My problem may be really obvious, but please understand that the actions I just performed cover almost the entirety of my server knowledge.

Is there something I can do to make short URLs work?[/]

OK, I tried the new one and here's what happened ...

1. Unpacked module.
2. Logged in.
3. Installed URL Rewrite.
4. Created blank .htaccess.
5. Went to "configure." Updated .htaccess. Both results good.
6. Clicked "done." Styles disappeared.
7. Navigated to album root. Received "Security Violation." Error details:

   Error (ERROR_PERMISSION_DENIED) :

   * in modules/core/classes/helpers/GalleryUserHelper_medium.class at line 207 (gallerystatus::error)
   * in modules/core/classes/GalleryCoreApi.class at line 423 (galleryuserhelper_medium::assertsiteadministrator)
   * in modules/core/SiteAdmin.inc at line 46 (gallerycoreapi::assertuserissiteadministrator)
   * in modules/core/classes/GalleryView.class at line 246 (siteadminview::loadtemplate)
   * in main.php at line 257 (siteadminview::doloadtemplate)
   * in main.php at line 46
   * in main.php at line 39

8. Clicked "Back to Gallery." Now at album root, but magically logged out.
9. Truncated address back to root and I'm suddenly logged in again.
10. Logged out deliberately by clicking "Logout."
11. Logged back in.
12. Turned on short URLs.
13. Same "No input file specified" problem as before and the styles remain gone.
14. Turned off short URLs.
15. Deactivated URL Rewrite.
16. For kicks, I clicked "configure" to see what I get. Under "Configuring your Webserver," I get the error:
    Because of your server configuration, we are unable to properly test whether mod_rewrite is properly installed.
    This is a result of trying to install gallery in a non standard directory. You need to edit
    line 6 in /my correct directory here/gallery2/modules/rewrite/test/mod_rewrite/custom/.htaccess
    and make sure it reads
    RewriteBase /cgi-system/php.cgi/gallery2/modules/rewrite/test/mod_rewrite/custom/
17. I check it and it reads "#RewriteBase /<Your Gallery Location>/modules/rewrite/test/mod_rewrite/custom/"
18. I uncomment it and change it to read my correct directory structure.
19. I click "Test Webserver Again" and get the same error.
20. I change it to what it told me to change it to and I still get the same error.
21. I cut my losses, uninstall the module, log out, truncate the address and all is normal.

Something I'm doing wrong?[/]