Wordpress Issue

So, this post is a bit off topic. It was brought to my attention that my single post pages were 404ing. This was an odd issue because my posts all showed up in the main page, but clicking any link would return an error. So I changed my permalinks from being Month/Day/post based to being the standard straight numeric method. After clearing the cache the page loaded fine; I tried the other possible permalinks and none worked correctly. I’m thinking that this has happened since my last wordpress upgrade. Anyone have any experience dealing with this?