@ Jerry
First, try going to the WordPress Permalinks settings admin page and click update, you do not need to make any changes. This will flush the cached permalink rules.
Second, do you have Sharabolic installed? If you do, deactivate/activate it. Another user just recently reported that plugin was cause 404/s.
Third, make sure you do not have a folder on the server that identically named as the page being requested. If a folder exists, the server will serve that instead of the page from WordPress. This too was just recently reported by another user.
These are my best guesses since this is not something I can get access to. Generally, search and permalink issues are nearly 100% a server config issue, something which I would have no control over as far as a plugin for WordPress goes.
Hope that helps!
Oh… one more suggestion… to eliminate the possibility of a theme or plugin conflict, temporarily deactivate plugins that are not Connections related and temporarily switch to one of the default WordPress themes, like TwentyTwelve.
