I managed to fix to the problem. First let me clarify what was wrong. Secondly, I will explain what worked for me.
The problem was I changed the permalink structure for a website that had existing posts. As a result, the pretty permalinks no longer worked for my posts although they continued to worked for pages. For posts, I would receive a message that said "sorry, no posts match your criteria." I installed the Advanced Permalinks plugin but it was not helpful.
THE FIX: The following are the steps I took to fix the problem
1. I went to plugin menu and disabled the Advanced Permalinks plugin.
2. I followed Marventus's advice and reset the Permalinks from pretty permalinks back to the ugly to default (Settings-->Permalinks, "Default")
3. I checked each one of my posts to see if they opened. They all opened but they had the ugly non-SEO friendly default url. I checked each of my pages and discovered that the pretty permalinks were no longer working for pages. They pages and posts had ugly, non-SEO friendly url's.
4. I went back to Settings and changed the permalink structure to custom structure and inserted the new pretty permalink structure (Settings-->Permalinks, Custom)
5. I checked each of my posts and pages. They were all working again with the custom pretty permalinks.
Marventus, thanks for your help with this. A helpful link: http://wordpress.org/support/topic/permalinks-not-working-how-to-restore?replies=14