Do you see the following?
If you don't then it may be the case that the policy change you have made has not made it's way down to the clients. If this is the case then can you tell me what installer did you use to install the SSC and Community server?
For the SSC you should down load AGAR-9RHDHN from fix central.
For the Community server make sure you have applied AMAI-9UACAJ as detailed in http://www-933.ibm.com/support/fixcentral/swg/selectFixes?parent=ibm%2FLotus&product=ibm/Lotus/Lotus+Sametime&release=All&platform=All&function=fixId&fixids=9001-ST-Community-FP-AMAI-9UACAJ&includeSupersedes=0
If you have the above applied then the problem could still be policy related and caused by problems when you registered the Community server with the SSC. Take a look at http://collaborationben.com/2014/12/05/sametime-9-policies-not-working-due-to-slashes-in-the-policy-name-in-ssc/
which I detail the relationship of policies.user.xml. You could look at policies.user.xml to see whether the change is in there to allow users to add external contacts. If not, then take a look at what I have done.