See ticket 694794.
Basically, the query to select the post IDs to rebuild actually blocks the query to update them. Because the select query isn't dependent on the update query, it doesn't cause a deadlock, meaning it will happily wait forever. On the flip side, I suspect this may also block post editing while the select query is running.
I resolved this by adding (nolock) table hints to the query for this install, but a more permanent solution is needed.