I have this issue as well (but in my case it says Page Not Found instead of 404 Not Found). Checking the slugs and resetting the permalinks did not work for me.
But I’ve also noticed that once you paginate to August it no longer has ‘Page Not Found’ in the page title but it has a body class of error404. Checking the landing Calendar page, I’ve found it’s also classed this way. So I’m assuming WordPress is recognizing the generated calendar page semi erroneously?
I’m using a mostly cosmetic Twenty Eleven child theme if that helps, would also appreciate more help with this.