I didn't see this mentioned anywhere so I thought I'd mention it here. I just had some difficulty while installing Omeka. I got the mod_rewrite is not enabled error and have just spent a ridiculous amount of time tracking down why. After testing that mod_rewrite was indeed working and trying all sorts of other things I discovered that the problem was:
My server didn't know its own hostname. Specifically, I was testing without using the fully qualified name. Once I added that to the /etc/hosts file everything worked splendidly.
ie. If my server is named myserver.mydomain.net then I was testing by simply using http://myserver/omeka/ which failed because at the very least 127.0.0.1 was not mapped to "myserver" although it was to "myserver.mydomain.net".
Lesson learned and I figured I should mention it here.