Looking at your site, I am still getting 404’s for the “more” (sitemap page) and WAN list, and “Contacts” shows the blog index (I’m guessing that is the only one you have actually tried to “rebuild”).
My suspicion is that the problem is .htaccess related. Do you have a copy of your “old” (working) .htaccess that you can compare to your current .htaccess files? Additionally, the interaction between permalinks and .htaccess is ususally the culprit in such situations.
This is not my area of expertise with WordPress, so I’m at a bit of a loss to know what to suggest next other than that.
You might find more useful help on your particular issue at wordpress.org (in the forums and the codex), for example, this thread and others seem to be related to your problem.
I would, since the re-install, again update my permalinks, and inspect the .htaccess file for potential issues - and then explore the WordPress support forums a bit for some more insight if that doesn’t work.
Another think I would do is to create and entirely new “page”, as a test, and see if the problem exhibits itself there also.
I agree that is not a very helpful response, and (assuming that you accurately described the problem) would make me think the support person either did not carefully read my description of the issue or did not actually “test” the site. I’ would respond back to that support ticket with additional information - I think you deserve a beter answer than that one.
–Good luck, and make sure and let us know what you find the problem to be.