categories giving error 404

Hello all

I am getting this error when I click on some of my categories:
TEETOOOT, ERROR 404
THIS IS SOMEWHAT EMBARRASSING, ISN’T IT?

It seems we can’t find what you’re looking for. Perhaps searching, or one of the links below, can help.

If I make a new category and a post for it I get the error. I also get it on my old categories but not all. The only thing I did yesterday was change permalinks from day and name to post name. But dont understan, if that is the reason, why some work and some dont. And new one dont work either.

What can I do?
the site is http://www.tarifasinternet.info