Cheers have done
It's all sorted. Worked out that there were some things checked out so tried to check them in and then purged the cache.
No wait it's happened again. Please use the same details as supplied previously.
Solved again. It was an ACL issue, the menu was set to special, hence when not logged in the error message occurred.
Problem again. Why did I say it.
Sorted again.
The issue I was having for those who may also have it, is that I had changed the "home" menu link from public, and apparently it should always be public. Sweet