Varsity game last night (8 man in Iowa)
The home team's kickoff return team featured a 3 man "wedge" and on a couple of the returns they actually held hands as they started up the field. They released hands a couple steps before they initiated any contact on a block.

Rule (2-3-10) states that "Interlocked blocking occurs when one player grasps or encircles a teammate just prior to or while blocking an opponent."

We flagged this once and then after discussing it, waved the flag off because (in our judgment) the R players had released hands several yards (about 3-4 yards in this case) prior to contact with any K players.

K's coach was livid, saying that the players can't (hold on to each other) at any point.

We plan to contact the Iowa association folks to get their interpretation. What do you guys think? This is the first time I've ever seen it in a game.

The rule says "just prior to or while blocking" and therefore it is your judgement. As you described it, I'd say they are fine. The coach was wrong in saying "at any point" and the rule shows that.

My OPINION is that if K1 and K2 were holding hands only as a way to guide each other up field and were not interlocked blocking. I understanding "just prior to" examples would be:
(a) K1 and K2 released hands at contact with R, or
(b) K1 slung/pushed/pulled K2 to privide additional force into R.

... but I have no additional sources to support these opinions. It is only how my mentors have taught me.

I don't have the rules book with me, but I recall that even though this is called "interlocked blocking" in the rule book, I recall that the signal for the foul is listed as the "holding" signal instead of the "helping the runner/interlocked blocking" signal.

Just curious as to why the rule book has it this way, especially when they're using the term "interlocked blocking" ??? (not to say that rule book is never wrong) :)

To update:
Our white hat contacted the Iowa association and their response was that as long as the players released (their grasp of one another) before any blocking, that that would be legal.

The same goes for New Jersey. A crew had called this foul last weekend and the coach called my President / Rules Interpreter who in turned e-mailed me earlier this week because I was the R for that same team last night. Of course it came up in my preGame conference with the coach. He said we hold hands and release just after the snap. I was told this was legal and told the coach not to worry it wouldn't be called this week.