I got past the internal error by changing my code to use the original trigger context map vs. having added to a new map.  

New issue is that I cannot update the case, from the email, on insert.  I can do it on update, however.

1) I fire the trigger on insert (create) - i.e. when a case is emailed to salesforce

2) I get the first email associated to the case

3) I parse the email body

4) I update the fields on case,  which only works on update

public with sharing class CaseParsingWorkflow implements TriggerWorkflow {

Map<Id, Case> newMap;

Map<Id, Case> caseMap;

List <String> parts;

String subject;

public CaseParsingWorkflow(Map<Id, Case> newMap){

this.newMap = newMap;

}

    private static Boolean hasExecuted{get{if(hasExecuted == null) hasExecuted = false; return hasExecuted;} private set;}

    public void execute()

    {

    if(!hasExecuted){

parseEmail();

    }

        hasExecuted = True;

    }

private void parseEmail(){

  Map<Id,EmailMessage> caseEmailMap = new Map<Id,EmailMessage>();

  List <EmailMessage> emails = [SELECT HtmlBody, ParentId, Subject FROM EmailMessage where ParentId IN: newMap.keySet() ];

        if (emails.isEmpty()) {

            return;

        }

        for (EmailMessage email: emails) {

            caseEmailMap.put(email.ParentId, email); 

        }

        String html; 

        for (Case c: newMap.values() ){

            EmailMessage firstEmail = caseEmailMap.get(c.Id);

            if (firstEmail != null) {

            html = firstEmail.HtmlBody;

            subject = firstEmail.Subject;

            }

        }

CaseEmailParser cp = new CaseEmailParser();

    parts = cp.doParse(caseMap, html);

    if(!parts.isEmpty() ){

    updateCase(cp);

    }else{

    return;

    }

}

private void updateCase(CaseEmailParser cp){ 

//get field vals from case parsing class

String country = cp.getCountry(parts);

String permalink = cp.getPermalink(parts); 

String caseType = cp.getCaseType(subject);

        for(Case c: newMap.values()){

         //update case fields - working on update

        }

}

}