I had a similar problem with both of my two iMacs. The latest update to 10.7.5 (in my case) solved this completely for one of them. The other TM still wasn't quite right.
I solved this by: going into System Preferences>Time Machine and moving the slider to the "Off" position. Then I right-clicked (Ctrl click) the TM EHD I use, on the desktop and ejected it. I removed the Firewire from the back of the Mac, then switched off the EHD (it is mains-powered in my case).
Left things for 5 minutes, plugged Firewire back in, switched on the TM EHD. Then into preferences>Time Machine and pushed the slider back to the "On" position. Hit "Back Up Now" and since then everything has been perfect.
Can't prove this will work for you, but worth a try.
Ian