Well Office 365 is based on Exchange 2010 and soon Exchange 2013, so I would say Exchange 2007 probably won't work with it. It's just Microsoft's way of forcing you to upgrade I'm afraid.
If it does work with Exchange 2010, maybe you need the latest SP?

