WP-Pagenavi returns 404 error

Both my premium theme I have and the default wordpress theme aren’t working when I go to additional pages of my news posts. I have over 50 posts in my posts page but whenever I click on the second page of my news (http://www.mmocraze.com/?paged=2), it gives me a 404 Not found error. The plugin is activated and I tried deactivating and reactivating it but to no avail. I have the default permalinks structure set (the ugly format: /?p=123) and no other permalinks rules configured….it’s all set on default. And like I said, when I switch to the original default wordpress theme, the page navigation still gives me a 404 error.

Any ideas?