Permalinks problem in 2.5.1 please help

Hi,
I upgraded to WordPress version 2.5.1.

I have set up myblog using default links:
http://www.fethiye-guide.com/?p=123

works ok

but when I change to any of the othert options
eg “month and name” and then hit “save changes”
it doesn’t work.

I mean the links get changed – but the pages are not found on the server.

My htaccess file permissions is set at 777

Is the permaling function broken in wordprss ?

Thanks