Cause his spoken lines, made more sense then what most of the other guys were saying, even athrun realised some shit after speaking with Heine. Also he was laid back outside of battle, but still authoritive. Even Athrun made the remark that Shinn would prolly behave more if someone like Heine was around all the time.
Also in battle he was kinda like Yzak.
Guess he was just an overall charismatic character.