I ran across this easy to follow tutorial which might help you pinpoint the problem.

http://www.wallpaperama.com/forums/how-to-test-check-if-mod-rewrite-is-enabled-t40.html

-Don-