I don't do any safe harbor match plans so forgive me if this seems too basic.

Employer uses the safe harbor match of 100% of the first 3% and 50% of the next 2% for everybody, including HCE's. Is that a problem? He is being told he has to give more to the NHCE's if he gives anything to the HCE's

What you are describing is a "basic safe harbor match ( other choices would all be called an enhanced match). When a document is prepared it will probably clearly state that this is the match paid to all NHCEs and HCEs.

I can't even imagine the mistake someone is making that would have them telling him that he has to give more to the NHCEs. Can you ask that person to give you something in writing?

1.401(m) (3) is the regulation to back up your position.

If there were other contributions to the plan the plan could lose it's safe harbor status for the year in question. However, it does not seem that this would apply based on the information provided in the original post.

If an employer only wanted to match the first 2% of pay for HCE's while giving the NHCE's a basic matching contribution, could the plan still be a safe harbor plan? In other words, is it required that HCE's get the same match as NHCE's

It is required that you follow the terms of the document. The document could be written to exclude the HCEs from the SH contribution entirely.