Turns out that you have to actually go into the sandbox (just refreshed from PROD) and recompile the subscribing trigger for SFDC to recognize it as available to the Platform Event subsystem.
In a way, this is like the use case wherein Schedulable classes are not available in the Force.com UI Schedule Apex Classes unless you recompile that class and/or run test methods against thay class. (I've seen similar SFSE for invocable methods not appearing in Process Builder)
UPDATE: This still seems to be true with triggers @V41 as of June 2018. Support tix filed
and Platform Events PM notified
UPDATE 2: From SFDC Support: With further investigation, I was able
to find few previous case where another customer had same issue which
was resolved by recompiling Triggers. On other hand, I also
acknowledge, these should be working after refresh. Please grant me
some time to actually reproduce these on my end and would raise these
up to higher experts to be addressed.
UPDATE 3: From SFDC Support: ...we have now raised these request to
R&D for further investigation
UPDATE 4: This is now a Known Issue. If you are affected or plan on using trigger subscribers to Platform Events, then please mark the KI accordingly.
UPDATE 5: Known Issue is now "scheduled" meaning that it will be fixed in Winter 19 Patch 4.0 (yea!)