Remote Time Machine restore issues

I picked up a new MacBook Pro today! The thing is super fast and only has an issue with the new trackpad (not wholly unexpected, more later)

I have a USB drive attached to a airport extreme as a time machine volume. This has been working fine for months.

I tried to restore from the time machine, but after 90 minutes, the disk was still being checked. Left only with a beach ball, I turned off the laptop, disconnected the usb drive from the airport and connected it locally to the laptop.

The MacBook Pro cannot see a remote time machine when mounted locally. Crud.

I then logged in and tried to mount the sparse bundle. 4 hours later the sparse bundle is still being checked.

Seeing as this is my data, I don’t want to skip the check. Just know that the sparse bundle has hundreds of millions of files and this verification step is slow.

What I do not know is if a time capsule would have this same issue. I doubt it, as the time capsule should know something about time machine, but I cannot verify this.

Do any of you have a time capsule? If you were to initiate a restore, how long is it before you can choose what you want to restore via migration assistant?