Page navigation don’t work with custom permalink

Hello to all! Well i have a blog http://averta.gr
When i have permalinks on /%postname% or /%category%/%postname%/ the page navigation don’t work and gives me 404 error.

When i set defaullt permalinks it works but this ain’t SEO friendly at all.
If i have custom permalinks “older entries” gives me link http://averta.gr/page/2
and when i have defult it gives me http://averta.gr/?paged=2

i disable all plugins but the same problem, a read a lot of stuffbut nothing helped. Thank you