Turns out your answer is pretty darn close...
I forgot to expose that method for COM interop, so EA could not find it when querying the COM interface (which it does seem to do by naming convention).
Specifically I expose for COM interop using something like this:
[Guid("INSERT-YOUR-UNIQUE-GUID-HERE")]
[InterfaceType(ComInterfaceType.InterfaceIsIDispatch)]
public interface _PluginGateway
{
//
// Addin events
//
[DispId(1)]
string EA_Connect(EA.Repository rep);
[DispId(2)]
void EA_Disconnect();
[DispId(3)]
object EA_GetMenuItems(EA.Repository rep, string menuLoc, string menuName);
[DispId(4)]
object EA_GetMenuState(EA.Repository rep, string menuLoc, string menuName, string itemName, bool isEnabled, bool isChecked);
[DispId(5)]
void EA_MenuClick(EA.Repository rep, string menuLoc, string menuName, string itemName);
[DispId(6)]
void EA_OnOutputItemClicked(EA.Repository rep, string tabName, string lineText, long id);
[DispId(7)]
void EA_OnOutputItemDoubleClicked(EA.Repository rep, string tabName, string lineText, long id);
[DispId(8)]
void EA_ShowHelp(EA.Repository rep, string menuLoc, string menuName, string itemName);
//
// Broadcast Events
//
[DispId(9)]
void EA_FileOpen(EA.Repository rep);
}