.htaccess and pretty permalinks, nothing works

I’m trying to get pretty permalinks working, and here’s what I’ve done:

-Tried various permalink structures, such as /%postname%/%postid%/
-Taken the code WordPress generates and pasted it in to .htaccess
-Had my hosting company enable mod_rewrite

WordPress changes the link structure of the blog, however, I get error 404s when I follow its links.

I’m getting Page links like this:

domainname.com/techie/

and Category links like this

domainname.com/category/tutorials

Please advise, thanks.