I can't remember exactly but it was a few hours. I already knew which week the issue arose (from comparing weekly snapshots) so that gave me a head start.

But yes, I built a lot of AMIs. And launched new EC2 instances for each of them -- it wasn't just a matter of rebooting since the first time an AMI launches there's different behaviour (both from FreeBSD, e.g. growing the root disk, and from EC2, e.g. disk caching).