I'm quite new to SilverStripe, but I've had a similar problem and will try my best ;).
1) You need to activate mod_rewrite in Apache's httpd.conf, both the module (but you have done that, otherwise the installer would complain on the first page) and AllowOverride. For your document root set AllowOverride to All. On my Windows pc it looks like this (c:/webserver is the document root) - not sure if this is great for security, but it's only a test machine:
Allow from all
2) Now you could test if mod_rewrite is generally working, just to make sure. Or skip this step if you are sure everything is fine.
I used the example of Bob and Alice from http://www.workingwith.me.uk/articles/scripting/mod_rewrite for testing (just copy and paste alice.html, bob.html and the .htaccess).
3) On my pc mod_rewrite was ok (step 2 was working), but I still got this error.
So I changed line 11 in "rewritetest.php" (directly in the Silverstripe directory) to this:
//@$testrewriting = file_get_contents('http://' . $_SERVER['SERVER_ADDR'] . $baseURL . '/' . 'InstallerTest/testRewrite');
@$testrewriting = file_get_contents('http://' . $_SERVER[HTTP_HOST] . $baseURL . '/' . 'InstallerTest/testRewrite');
I think the problem was that my apache is bound to port 8080 and server_addr disregards the port (but I might be wrong :D).
Anyway, this worked out for me. Hope it can help you as well.
PS: Tested on Win XP, Apache 2.2.4, PHP 5.2.1, MySQL 5.0.27