Are you positive that your web host has the mod_rewrite module installed on the server?
Feyd is the htacess expert around here so until he gets back here are a few links to check out:
CodingForums Supreme Overlord
All Hail Spookster
Who gave you that Ugging infraction? Yeah that's right it was me!