I had a previous backup of my entire MBP with Snow Leopard. Then I upgraded to Lion, and plugged in the Time Machine for the first time.. It took 45 minutes for the ´Preparing Backup´to go away, and then it started backing up things. It got stuck at 857 bytes for about 10 minutes.. then it continued backing up stuff at a 10mb per minute rate (Very slow compared to Snow Leopard) .. It took me 5 hours to backup 7gigs of stuff.
After that, every backup started being faster, like it was on Snow Leopard..
So don´t worry, the first backup is the worst.