Hi,
I had the same problem — I found the answer in the WP Codex, which says the .htacess file should go in… “in the directory in which your main index.php file resides. For example, if your WordPress blog is installed at domain.com/wordpress/, put the .htaccess file at domain.com/wordpress/.htaccess”
Copy the contents given for the .htaccess file in the window where you set the permalinks, paste it into a text file, save as .htaccess and FTP it to your main WP directory as above.
Rob