Remember: Please write in the comments area whether or not you had success with this solution, and share other ideas.

Issue: When clicking on “Older Posts” which brings you to the URL “page 2” (page2), you get a 404 error page.

Problem: Apache mod_rewrite is disabled –or– “AllowOverride” is set to “none” in your Apache configuration file for the virtual server.

Solution: In my case, the problem was with AllowOverride being set to none.

Simply look though your Apache configuration file, and change “none” to “all” for AllowOverride.

Here is an example of what this should look like:
DocumentRoot /var/www
<Directory />
Options FollowSymLinks
AllowOverride all
</Directory>
<Directory /var/www/>
Options Indexes FollowSymLinks MultiViews
AllowOverride all
Order allow,deny
allow from all
</Directory>

WARNING: You should only change AllowOverride to all for the web directory. (Exclude all other items, such as CGI or usr/share/doc). Leave these alone!

Solution 2: This second option works, but does not fix the underlying problem.
Go to your Permalinks settings page in WordPress. Under “Custom Structure”, add /index.php before the line.
Eg:
/%year%/%monthnum%/%day%/%postname%/
should look like this:
/index.php/%year%/%monthnum%/%day%/%postname%/

All links will go through index.php. If you change these links back to not having index.php, they will still redirect properly.

Solution 3: Go without custom permalinks structures.
The disadvantage is that Google doesn’t like these, since the actual link tells Google nothing about the page. For higher ranks in searches, you should avoid this.
Simply go to the Permalinks settings page in WordPress, click “Default” and save changes.

A general reminder: It’s usually a bad idea to constantly switch permalinks. It places you farther behind in Google because your links are always becoming broken. Choose a structure, and stick with it!