"I dropped all the foreign key constraints to this table on the handful of tables referencing it. I dropped the index, and then I added the foreign keys references back."

I would like to point out that if you didn't use WITH CHECK CHECK to fully rescan those tables and revalidate the constraint, those FK's are untrusted by SQL Server, and do not provide their full benefits.