All posts, pages, and categories resulting in 404 after 3.1.2 upgrade

Hi all,

My site has been working fine for many years, I have been using the following permalink structure /%category%/%postname%/ with pathless categories plugin. However I upgraded to 3.1.2 today and since that time all my pages and categories and even posts are resulting in a 404 error.

I have checked my .htaccess and nothing has changed, so i took the following steps…

1) Deleted the current .htacess and then set the permalink structure to default in wp-admin, this DOES load the pages/posts.
2) Went back and changed the permalinks to my custome structure of /%category%/%postname%/ , this correctly updated the .htaccess but everything results in a 404 error
3) Tried the above with the pathless categories plugin disabled

I just cannot seem to get my permalinks working in the way that they were, and it doesn’t make any sense since i know the .htaccess hasn’t changed. Does anyone have any idea what i can try next?

Thanks