This is a 1.0 bug report, so it may have been fixed in 1.0.1.
Anyway, I set my options -> permalinks to Yyear%/%monthnum%/%day%, and go told that I should use some cockamamy mod_rewrite rule that spat out year=$1&monthnum=$2&day=$3.
Unfortunately Wodpress didn't think this meant what it said. I kept getting various posts from May of 2003. A given link would always get the same post, but no link fetched a post that wasn't from May of 2003.
I finally got tired of diddling with it, read teh RREADME file and put in my own mod rewrite rule:
it works like a champ.