I don't get how that works. cart/checkout/shipping/quote should be inheriting its access from cart/checkout, which is also user_access('access content'). Also, if it was really a permission problem, you wouldn't be getting the 404 Page Not Found error. It'd be an Access Denied.

I'm starting to think that your menu cache had been corrupted somehow. It's very strange.