Ash, I managed to solve the problem on my installation. What I did was modifying thefile.
RewriteRule ^story/([0-9]+)/?$ story.php?id=$1 [L]
In the beginning and the end of the block regarding 2, it seems that something is overriding this, so putting it again at the end, made it right. Well that's my dirty fix