The only thing that you are not entitled to store is your coat, technically. Pre-boarding is not just a privilege so you can sit down first; if you are there first it should be your space. It was nice that the FA was being proactive to try to accommodate passengers, but if the guy is cheating with carry-on he should be subject to the consequences associated with breaking the rules.

You could have tried explaining that you are an elite and that you are already did your part to be considerate, by only having only one tiny bag. I don't know if you would have gotten you anywhere, especially between LAX and EWR, but it is always worth a try.

One more thing, you are gold, 6'6, and you did not reserve an exit row?