After calling drupal_flush_all_caches, menu items with access callback TRUE are giving access denied error
The answer lies in some custom code I wrote to understand why some unrelated things were issuing an error. I discovered it was this when I was copying the code to my test site and then putting in this new code which resulted in the same issue on the test site. So that is how I was able to narrow it down. Going forward, I am going to have 3 sites, one for new development, one that mirrors the live site, and the actual live site. The issue comes from being in the middle of upgrading modules on the test site and so I couldn't really use it reliably to test new code, so I would code it on the live site (a big NO-NO and I really shouldn't have done this). The only reason I didn't my custom code was an issue was because I hadn't cleared the cache in a while, so the menu items were still available. 

Maybe this will help someone in there processes to not be dumb like I was.