For me, it was the fact that he didn't live up to the mental image I had built up about Legolas and what he should look like. Most of the other characters I could live with being as they were, not too different from my book image.
Legolas was the only one who was too far withdrawn from my original idea of what he should look like.
I, of course (and I assume everyone else) thought he looked like
this. Didn't you?
On a serious note, I think that, as with most running gags, it stemmed from lost roots and is now a well established joke and will go on until everyone is tyred of it.