Update: Please ignore this post, I was able to get it working. The issue was that I had a Page located at the base URL of where the archive would be (as I wanted custom index handling), and changing the Page URL temporarily fixed the issue again.
None of my custom post type permalinks (which use the default WordPress URL handling option) are working after the upgrade to 3.5. I also upgraded to the latest version of Types, so everything should be current. Is this a known issue?