CLEO 6.0.2 has the option to turn off the check for FEBE on startup. When (or if) the message box appears, there is an option to "Check for FEBE on startup". Unchecking this box will force CLEO to avoid the version checking. If the version checking is off and you do not have the correct version of FEBE installed, CLEO will simply not work correctly (or at all).

If the version checking is off and you would like to turn it on again, change the preference extensions.cleo.checkforFEBE to true in about:config.
The problem seems to occur when CLEO is trying to get information about FEBE. I've run into this problem before (i.e., when older FEBE versions would display a message about not being able to load extension data). Firefox's AddonManager.jsm routines run asynchronously and don't always return results in a timely manner. Sometimes it does, other times it doesn't. I cannot duplicate the issue so it is hard to debug. This fix just eliminates the checking all together.