The loop itself naturally even in a category, or tag or for recent posts should work fine on your most recent posts. What you are doing is the same thing StudioPress has done in some of their themes when it is not necessary to use the custom WP Query when the natural WordPress loop will work and display the most recent posts.

Even using the custom query, it will call the same exact thing to the page no matter if it is page 2, page 3, and so on.

You would only need a special query if you only want to display a specific category or custom post type, or even from tags.

Then you can put in plugins like WP-PageNavi or others that you want to use ( like the navigation I use at blondish.net at the bottom of the front page, and similar to what you are trying to put on yours.) That is using a normal WordPress loop to call the most recent posts. ( http://codex.wordpress.org/The_Loop )

Side note- If you need me to give hands on help, drop me a line.