Clean Lion install, keeping Time Machine history?
I think you'd be better off doing a clean install and using Setup Assistant to copy over just the users and settings.  (Setup Assistant, like Migration Assistant, can use a Time Machine backup as the source.  The are basically the same application, but Setup Assistant configures your Mac for the first time and Migration Assistant helps you copy stuff over to a Mac you've already set up.  You can only use Setup Assistant immediately after a clean install of the OS, which of course includes the first time you boot up a new Mac.)  That way for sure your new users will have the same UID and UUID as your current users, meaning your backup and all your other drives ownership and read/write permissions will still work as before, and there's a chance that the Time Machine interface will work to fetch old files.  I wouldn't bet on the latter, but I've had permissions problems before when not migrating users.  Of course, this might be different if all your machines only have one user; my machines have 3. 

I'm pretty sure, also, that if Time Machine doesn't work straight off the bat, you can trick it into working by replacing the com.apple.TimeMachine.MachineID.plist file in the  Time Capsule's sparsebundle disk image for the backup for the machine in question.  But that's a bit advanced and certainly unsupported, so I'd leave that for "when all else fails".