I wanted to post this because I saw quite a few people having the problem that I was having. I managed to find one thing that caused my problem, as opposed to disabling this plugin or that plugin, none of which I had installed.
When changing the default permalink configuration from ?p=5 to /2013/05/my-cool-post, all of a sudden the links to both the posts themselves and to the comment buttons were giving 404 errors. After much searching.
Some people reported having multiple sites hosted in the same wordpress account or hosting account, but only having this problem with 1 site. This tells me that it is specific to the site, not the hosting provider, or even WordPress. That's what led me to the solution.
While perusing through the httpd.conf file on my system, I was looking at the following:
<Directory /> Options Indexes FollowSymLinks Includes +ExecCGI AllowOverride None </Directory>
Notice that "AllowOverride None" is set, which basically disables mod_rewrite (an apache module necessary for WordPress to be able to rewrite your urls -- ie use Permalinks). I changed this to "All", and restarted httpd, but still had the same issue.
Finally I went through and searched for "Directory", and there are quite a few of them in there, but then I found another stanza:
With quite a few comments inside of it. (That's why I didn't notice it the first time around.) Inside that Directory stanza, was this:
This one was overriding the "/" directive earlier, so as soon as I changed this from "None" to "All", and restarted httpd, my links worked perfectly afterward.
I hope this helps you guys, it seems to be a chronic problem in WordPress.