Permalinks & Blank Next/Previous Page Links

Hello,

I have been having an issue with my blog for some time and after countless hours trying to find a solution, I feel like I need to ask the experts for some help! 🙂

I write and manage a blog for my company which is currently using WordPress version 2.8.4.

I recently noticed that the previous page and next page links are no longer working.

Clicking on the previous page link at the bottom of the page takes me to http://blog.mydomain.com/page/2/ but it is just blank page.

The permalinks are currently set as http://blog.mydomain.com/2011/11/03/sample-post/

If I change the permalinks to http://blog.mydomain.com/?p=123 then clicking on the previous page link gives http://blog.mydomain.com/?paged=2 which works with no problems. However, I prefer to use the aforementioned permalinks as the blog is already quite established with lots of incoming links. Furthermore, I am sure that they used to work previously.

Deactivating all plugins and reverting to the default theme does not resolve it.

Furthermore, this issue does not apply to previous pages when browsing posts from the category view.

I have a feeling that this issue is due to permissions somewhere. About a month ago, I tried to update to the latest version of WordPress, but had a problem with the host servers version of PHP being too old to be supported. Hosting is managed by an old member of staff who is impossible to get hold of so I ended up reverting back to 2.8.4. I noticed since then that I had permission issues when trying to create new image folders in the wp-content folder. I have fixed that by changing permissions of the preceding folders which seemed to work.

Is there any way that I can fix this previous/next page issue? We are releasing a new version of the companies main site in the next few days and I would like to blog to be working as well as possible for then.

Thank you very much for any help that you might be able to offer!