Yes, it is normal for that particular reconvergence to take longer, since it is a normal STP calculation.
UplinkFast is an STP Root Port optimization, meant for access switches on the edge of your network, not core or distribution switches acting as root bridges or backup root bridges. It speeds up reconvergence at the edge switch whenever a redundant connection that is directly connected to the edge switch fails.
When your edge switch has two connections providing redundancy, one is forwarding, and the other is blocked. But when the edge switch is also running UplinkFast, it knows which port make active if the current forwarding redundant link goes down for any reason, and can short-cut the calculation.
Reasons the forwarding link could go down: the link itself fails (cable is cut or disconnected, or a port at either end is shutdown or fails), or the switch at the remote end goes down (which "fails" all its ports). You have simulated both of these scenarios in your tests, and seen the expected results for UplinkFast.
When you powered up the root bridge again, both it and the backup root bridge had to work out who was going to carry on being the root bridge. UplinkFast is no use on those switches, because a root bridge by definition has no root ports, so there's nothing for UplinkFast to optimize. Therefore, the two possible root bridges have to go through a regular STP reconvergence, which takes longer.
Your edge switch must wait until the two core/distribution switches figure out which one is going to be the root again, now that they're both on. Once the network reconverges, the edge switch can work out its UplinkFast root port optimization plan again.
Here's another test for you to try: with all switches up, disconnect the link between your root bridge and backup root bridge. I predict you will see the same long-duration network blockage that you noticed before. Once the network stabilizes, wait a bit, then reconnect that link; you'll see that same long blockage interval.
UplinkFast on your edge switch cannot help you when the STP failure is on an indirect connection, that is, one that is not directly connected to the switch running UplinkFast. Cisco has another feature, BackboneFast, which can help cut the time down and deal with indirect failures; but all switches must run it, and not every Cisco switch can.
You can shorten the reconvergence time in your core a little if you tune your hello time, max age, forward delay, and network diameter settings. (Technically, max age and forward delay should be derived from and agree with your hello time and network diameter; but not all switches let you specify the network diameter directly.)
Sounds like your network is simple enough that it would be easy to do. Set hello time to 1 second (default is 2), and network diameter to 3 (default is 7); resulting safe max age value is 8 seconds, and forward delay is 7 seconds (6.25 seconds, actually, rounded up; default is 15). This will keep your worst-case reconvergences in the 14 to 22 second range, instead of the default 30 to 50 seconds of Spanning Tree. Make these changes on your root bridges. CAUTION: As you add more switches to your network, you may have to adjust these settings depending on where you add them.
On second thought, it's probably better to just leave these settings as they are, and continue to leverage UplinkFast on the future edge switches.
Hope this helps.
