First off, permissions in Tiki can be very confusing, it does take some time to understand them fully, so don't be too discourage if everything doesn't make sense immediately!
To address your problem, I think it's normal that the anonymous users can't see the Sandbox item on the menu because the menu is probably working from global permissions and not category permissions.
First verify that anonymous users do indeed have access to the Sandbox by logging out and going directly to the appropriate page. You should be able to replace the page portion of your URL (probably tiki-index.php) with tiki-editpage.php?page=sandbox.
Assuming that works ok then you've basically got everything set up correctly, you just need to edit the Sandbox menu item (tiki-admin_menus.php) to ensure that it isn't checking for permissions that anonymous users won't normally have. I think the default menu (which I assume you're using) requires the permission tiki_p_view in order to be able to see the Sandbox item. You can simply remove this permission when you edit the Sandbox menu item.
If you need more help then let me know.