Tres. Reg 1.106-1 states that "..the gross income of an employee does not include contributions that an employer makes to an accident or health plan for compensation(through insurance or otherwise)to the employee ..."

"... on a policy of accident or health insurance covering one or more of his employees,.."

Can new employer pay COBRA premiums for new employee relating to COBRA continuation from their prior employer and have the premiums be excluded from ee's income?

It appears there is no requirement that the employer actually be the sponsor of the plan that premiums are being paid to, only that the plan covers at least one employee, which it does, exactly this one employee.

Anyone know whether this is excluded from income or treated as taxable compensation to this employee? Thanks.

Yes, it works. In fact, it is pretty common for small employers where it is very likely that the newly-hired employee (or their dependent) will encounter significant medical expenses. It is much cheaper (in the long run) for the employer to pay the premium than to have the employee in the plan.