Major Issue with WordPress

Hey

I created a blog about a 1 month or so ago and it was all going great until my previous posts link broke and goes to a 404 page! Now this is a major issue as people aren’t able to read older posts. I have tried changing the themes and nothing worked.

The blog is here http://www.corporate-gifts-co.com/blog/ and at the bottom of the page the previous posts link is broke. Does anyone have a fix for this? It is really important.

Thanks