I had exactly the same thing happen to me when I started with WP - permalinks are a very important feature for your website/blog, they are worth a bit of sweat and tears to get working!
Im running on FreeBSD/Apache and found that I had to put the following in my .htaccess and then make it NOT writable. This has been used on lots of WP installs and works fine for me.
# BEGIN WordPress
<IfModule mod_rewrite.c>
Options +Followsymlinks
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
# END WordPress
I think the main difference between this and the standard WP .htaccess (from memory) is the line:
Options +Followsymlinks
I set the permalink options in WP, then replace the text in the .htaccess file with the above and make the file NOT WRITABLE - if the file is overwritten by WordPress it breaks the site every time! I'm then able to change the WP permalink structure (or update it if a plugin requires) no problem. WP warns that you need to update .htaccess (because it couldn't write to it) but I don't and it always works fine for me with many WP installs!