Sounds like mod_rewrite is either not installed, or not enabled in httpd.conf
Seeing are you're running xampp (right?) it's probably the latter. Find httpd.conf, and then find the line
or something to that extent. Than uncomment that line and restart Apache (or xampp, if that has a restart option -- I've never used it myself).
I have enabled the mod_rewrite module in the xampp/apache/conf/httpd.conf file.
When i search through the httpd.conf file, the "AddModule mod_rewrite" line is absent from the file by default. When I add that line, Apache just doesn't start up giving an invalid command error.
I went through the tutorial in your signature. Your first example is about test page (test.html and test.php). But it gave me the same problem.
I have also changed "AllowOverride None" to "AllowOverride All" as you mentioned.
I will go through it once again.
Here's my httpd.conf file.