After reading both notices, this doesn't seem to be possible, after a plan year has started. That doesn't seem logical since the participants would be in essentially the same position, but with an enhanced benefit. Does anyone have any insight into this issue?

Would it change matters if employer did not give SIMPLE notice before beginning of year?

See Notice 2000-3. Generally amendments to an existing 401(k) Plan must be made prior to the start of plan year.

The fact that Notices for the SIMPLE Plan were not distributed timely does not the change the answer as to Safe Harbor. You still have an existing 401(k) Plan.