The problem: redirecting to /index.php instead of /mambo/index.php was because I had "ErrorDocument 404 /index.php" in the .htaccess, this should have been "ErrorDocument 404 /mambo/index.php"

It might be a good idea to specify this in the installation docs.
After I fix this though, when I click on an article, I get an error as "FILE NOT FOUND: /mambo/Newsflashes/Newsflash/Newsflash_2.htm" in the mainbody block (where the article was supposed to be displayed), just below this error, I get the article titled 404--which I created for installing 404 Sef...
Now, when I look at the database, mos_redirection table contains:
Newsflashes/Newsflash/Newsflash_2.html in the oldurl column. However, as you can see from the error above, in process_uri method of sef.php, $_SERVER['REQUEST_URI'] returns the URL with the subdirectory, which is:
/mambo/Newsflashes/Newsflash/Newsflash_2.htm, so the database lookup returns empty there... And I think that is why it fails there...