6.5.1 has reached its end of support last year. I'd consider upgrading.
Meanwhile, I assume you verified that Sametime ports are open on the external firewall. Your external users can enable Java console (http://www-01.ibm.com/support/docview.wss?fdoc=wplcsame&rs=477&uid=swg21086819
) to see what they get. They can also try telneting to your Sametime server on 1533 and 8081 and see if they can get through.