ebriet's tip helped me. My first Lion backup was taking 14 hours and was only half way before I stopped it. After reading ebreit's tip, I updated the Time Capsule in the airport utility screen and the same backup then took only 6 hours. Strange that Time Capsule doesn't update like the rest of the system in Software Update - this was the first I knew that it could be updated.
Also - why isn't Apple improving Time Machine? It's been stuck on the same useless every hour scheudule since it was released. That simply isn't good enough - when working on graphics or video (two of the main uses for macs) hourly backups slow the machine down significantly and often take more than an hour - so you're using a ridiculously slow maching the whole time you have Time Machine turned on. The only solution as it stands is to turn Time Machine off and do manual backups when you remember. The problem then is that Time Machine often loses its indexing or something and every backup seems to start from scratch and take hours, rather than just backing up differences. So there isn't much point in Time Machine if you actually use your Mac!