Well this was a minor annoyance I could have done without. Fortunately the solution is very simple.
If you are trying to SHARE a Calendar in Outlook and you receive the dreaded:
Calendar sharing is not available with the following entries because of permission settings on your network
you have likely typed the recipients email address in or used the address from your cached addresses. That will not work. What you need to do is click the TO button and select the intended recipient(s) from your address book. I used a corporate GAL and bingo all was well.