Did you read this post from Leonid ?

"Usual reason - missing mod rewrite module in your server. You should install it or disable all options in admin panel->permalinks section."

That is maybe the solution to your problem...