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