I had this problem as well after updating to Lion. Updating used to take only a few minutes (particularly if nothing had changed), but suddenly it took like half an hour. The Time Machine icon showed "preparing for backup" most of this time.
The time machine logs can give more insights into what is causing this problem (start console, type "backupd" in the search form). In my case "waiting for index to be ready" took a lot of time. This appeared to be due to a problem with Spotlight.
I got it fixed by turning off Time Machine, resetting Spotlight for both the system and the TM (this involves Spotlight rebuilding it's databases, which may take several hours), and then turning Time Machine on again. After that, updates took only a few minutes. I fixed my TM shortly after upgrading to Lion, so everything has been working without any issues for about a week now.