I have a third-party NAS drive (Western Digital MyBook World II) which I used for time machine backups in Snow Leopard. I've upgraded to Lion and the first backup has spent over an hour 'Verifying Backup...', what is OS X actually doing here and if I choose to skip verification what are the consequences? It seems to be stuck on 69%...
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.