I encountered some issues accessing Lync in O365.  I ran the connectivity test (at:  http://support.microsoft.com/kb/2409256) and noticed that even though I created an “Allow outbound” rule through TMG, the tests were failing.  So, I went through the TMG config and opened up the ports identified by the test.   See attached pdf for TMG config steps.