Thanks Gordon, this one is specific to IE, another is specific to communities, we're using neither.

I did find a work around, which I think lends credence to the idea that this is a bug with how Salesforce is parsing the JSON from the parameters attribute of <apex:canvasApp>

Summer '15 solution: 1 line in visualforce:

<apex:canvasApp developerName="Canvas_App_Name" height="900px" width="1050px" scrolling="auto"
   parameters="{p1:'{!Obj__c.Account__c}', p2:'{!Obj__c.Order_Num__c}'}"
   />

Winter '16 solution: 1 line in visualforce, 1 APEX LifecycleHandler class, 1 APEX test class:

In order to pass the parameters correctly in the signed request, it's now necessary to grab what's in the apex:canvasApp parameters attribute, then re-encode the JSON in APEX:

First the VisualForce, change the parameter names to something else - I changed "pram1" and "pram2", which are what our external app expects to "p1" and "p2"

<apex:canvasApp developerName="Canvas_App_Name" height="900px" width="1050px" scrolling="auto"
   parameters="{p1:'{!Obj__c.Account__c}', p2:'{!Obj__c.Order_Num__c}'}"
   />

and the APEX, where we set the parameters "pram1" and "pram2" again. 

public with sharing class LifecycleHandlerClassName implements Canvas.CanvasLifecycleHandler {
	public Set<Canvas.ContextTypeEnum> excludeContextTypes(){
        return new Set<Canvas.ContextTypeEnum>();
    }
	
	public void onRender(Canvas.RenderContext renderContext) {
        Canvas.EnvironmentContext env = renderContext.getEnvironmentContext();
        Map<String, Object> currentParams = ( Map<String, Object> ) JSON.deserializeUntyped(env.getParametersAsJSON());
        env.setParametersAsJSON('{"parm1":"' + currentParams.get('p1') + '","parm2":"' + currentParams.get('p2') + '"}');
    }
}

Of course, this now requires APEX test coverage:

@isTest
global class LifecycleHandler_Test {
    static testMethod void LifecycleHandlerOrderParts(){
        // Test handler with some mock environment context values
        LifecycleHandlerOrderParts handler = new LifecycleHandlerOrderParts();
        handler.excludeContextTypes();
        Canvas.RenderContext mock = Canvas.Test.mockRenderContext(null,null);
        // Directly update the mock RenderContext and set the custom parameters
        mock.getEnvironmentContext().setParametersAsJSON('{\"p1\":1,\"p2\":2}');
        Canvas.Test.testCanvasLifecycle(handler,mock);
    }
}