Custom Permalinks Creates all 404 error pages

Hi,

I have been trying to change my permalink structure to a custom setting of /%category%/%postname%/ but everytime I change it to anything except for the default structure all pages show 404 errors.

I have checked the links and they seem to direct to the correct page but it still shows a 404 error. How can I fix this?

My site is currently located at d2g.kamiya.com

thanks