How late in the calendar year can an employer establish a SIMPLE-IRA plan, considering the 60 day notice requirement and the requirement that a SIMPLE plan can only be effective between Jan 1 and Oct 1??

October 1 is the latest you can adopt the SIMPLE.

When would the 60 day notice have to be given to make a simple plan effective by 10/1? Or does the notice period apply? I know that for safe harbor 401(k) plans the notice requirement is tied to the effective date of the plan, but is that true with simple plans as well?

I'm going from memory here - always a dangerous thing to do, but as I recall, the "60 day" election period, for the first year of a SIMPLE plan, must include either the date the employee becomes eligible, or the day before.