Hi Paul,
I realise this is old now, but it may help others as I've stumbled across it from a search - I think the reason yours was not responding to removing the guest permission from the navigation block was probably due to either one or more of these settings being something other than the default values:
- Site administration --> Front page --> Front page settings --> Default frontpage role
- Site administration --> Users --> Permissions --> User policies --> Role for visitors *and* Role for guests
I am not 100% certain which combinations would work in your specific scenario, but the removal of guest permissions on a block has the desired effect when these settings have default values.
Regards,
Martin