When Time Machine says it's 'Verifying Backup...' what is it actually doing?
If it's your first backup in Lion, you need to leave the computer awake and connected to the Time Machine volume and let it do its thing, perhaps overnight. Once it makes an initial backup it has to construct an elaborate index database so that the Time Machine restore functions can work correctly. If you interrupt or cancel the process, it will have to start over from the beginning again at some other time, and this will indeed take up time and system resources. I have heard complaints from others that the initial backup, verifying, indexing, etc. takes a great deal of time in Lion, but you need to allot the  time necessary to let the system do its thing in order that it work correctly.