I tried the custom structure, but when I stripped out the "index.php" part, all I got was - "Page not Found".
And now for the puzzling part - this happened with only newly installed WP blog. On an older blog, the permalinks have remained what I had set as custom structures - even when I updated the old blog to 3.0.4.
Is someone else getting the same issue? I would appreciate any help in this regard. I tried our mutual friend Google, but most of what I read escaped over my non-techie head.