Actually, the permalink structure you're using
doesn't require .htaccess rewrite rules (that's why it's still blank). This structure previously caused problems in WP 1.2.x & 1.5.x, but it's much more rare with 2.0.x, so there may be other factors at play.
Without a URL to play with, it is more difficult to figure out what the specific problem for your website is. I would suggest changing the permalink structure to something else (removing the index.php portion) to see if it still gives you the same error. Be forewarned that you will need to update the .htaccess file for the new structure.
If the feeds start working, then you'll know it's a problem using index.php and if not, it may be a feed specific problem or even a problem with your content.
~ Teli