FCE 3.5 and Lion
FCE 3.5 WILL work with Lion. It's binary code. HOWEVER, you cannot install from the disk on a Lion machine as the Installer, if you can believe it, was written with PowerPC code (who would have thought?). So, when you get your machine, be sure to use the migration assistant and you should be fine. If not, you're in trouble. Otherwise, you CAN get it installed on Lion, but it's the complicated process of installing it on Snow Leopard first, then upgrading to Lion.
Better yet, if you can simply stay with Snow Leopard, you'd be better off for the time being. The FCE 3.5 installer isn't the only problem you'll have with Lion. Apple really screwed this operating system upgrade up for users.