Enable Lync On-Premise to Federate with Office 365 Lync Online
By default the On-Premise Lync installation is not enabled for communication with Office 365 Lync Online, even if you have enabled open federation on both installations.
Tom Arbuthnot has a great post ]How to enable Lync On-Premise to Federate with Office365 Lync Online]1 on how to solve this issue, and I would recommend everyone with an On-premise Lync installation to follow the instructions.
30.09.2011 EDIT: Updated link to article as Tom Arbuthnot are moving his blog over to lyncdup.com