Getting 404 Error pages on every page but homepage since new year

I guess the title sums it, but no one can access any blog post (as in clicking the title to view the post itself), page 2 of the homepage (for the next 3 blogs), pages, pages for tags, and so on.

I don’t know why it’s doing that. I contacted my host and they said they would reinstall it but didn’t. I really really don’t want to install it all over again.

http://www.rhymeswithsteve.com/

Any ideas on what I should do? Your help is greatly appreciated.