Permalink error

Hi,
I have installed latest versions of Ubuntu + LAMP and WordPress.

Everything works great exept when I change the permalink settings. If I change it to anything from “default”, I get the “HTTP 404 Not Found” error when going to the site/page.
From the beginning I didn’t had a .htaccess file, but I have created it and added the correct permissions, but it still doesn’t work.
I also read this theread and tester everything in it:

http://wordpress.org/support/topic/pretty-permalinks-and-htaccessgt-404-not-found-errors?replies=11

But I still get the 404 error when changing Permalink settings.

Does anyone know what the problem could be? Thanks for any advice.