I spent quite a bit of time troubleshooting why
traceroute mac sw1_mac1 sw2_mac2
works in one direction from C3850 switches to C1000 switches and
traceroute mac sw2_mac2 sw1_mac1
does not work, timeout every time.
Ultimately I came across a priceless post here that there is
show running-config all
which shows the default settings.
After comparing C3850 and C1000 config files I found the solution:
l2 traceroute
That's it, on C1000 by default L2 Traceroute is disabled while on C3850 it is enabled.
Those struggling with L2 Traceroute, just need to run this command and it does the trick:
l2 traceroute