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).

Thanks for the additional information, a few hours sounds great, I was expecting multiple days to narrow it down, given a lengthy feedback loop.