[SalesForce] Test case failures due to VF email template

First, a little background information: I'm working on an end-to-end custom quoting solution that leverages the standard Quote object. We also utilize Sterling CPQ, which serves as the end-state for all quotes created using our VF page (the Sterling mashup is a little sluggish and lacks a few features that are much more easily-implemented by our custom solution). Users will create a standard Quote record using the page, and after they're satisfied with the changes they will be "promoting" the record to a CPQ quote.

Other unnecessary details aside, we have this process working quite well. That is, until I decided to add a Visualforce email template into the mix. An email alert that goes out upon successful Quote promotion previously used a standard HTML email template and things seemed to work fine…the email was sent out as it should have been, and test cases executed with no problems. However, because I wanted to show fields on other related objects without adding a bunch of formula fields to the Quote object, I decided to swap the email template out for a VF email template. Manual testing continued to work just fine, but now our Apex test executions are failing with the following message:

System.DmlException: Insert failed. First exception on row 0; first error:
    INSUFFICIENT_ACCESS_OR_READONLY, user does not have access to use approval
    assignment email template: []

I should note that we are not using any kind of approval process on the Quote object or a custom Apex controller for the VF email template, which is why the solution to this question didn't seem to help much. I also found this on the community boards, although I haven't attempted to deploy the application to production yet, since the test case is failing in the sandbox in which it was developed. The header for the email template looks something like:

<messaging:emailTemplate 
    subject="Proposal for Opp {!relatedTo.Opportunity.Name} Promoted to Quote"
    recipientType="User" relatedToType="Quote">

Has anyone seen something like this, where text case execution works fine with an HTML template but not with a VF email template? Please let me know if I can add any additional information.

Update: Here's a watered-down version of one of the test cases that is failing. The failure never indicates the line number, but it would have to be at Test.stopTest(); because the call to promoteToQuote right above it is a future method and its execution would be delayed. The future method normally would make a webservice callout, process the response (although in the case of test execution, it uses a mocked-up response), and then update the quote record's status to "Promoted" if successful (this condition is what the workflow rule in question fires on, and that's the only place where it would be getting set to this).

static testmethod void testPromoteToQuoteSuccess() {
    User usrAE = UnitTestUtil.createAE();
    insert usrAE;
    System.runAs(usrAE) {
        Account a = UnitTestUtil.createAccount();
        insert a;
        Opportunity o = UnitTestUtil.createOpportunity(a.Id);
        insert o;

        Quote q = new Quote(OpportunityId=o.Id);
        q.Proposal_Status__c = 'Active';
        q.Name = o.Name + ' - Proposal';
        insert q;

        Test.startTest();
        ProposalHelper.promoteToQuote(q.Id);
        Test.stopTest();
    }
}

And of course there are a bunch of assertions made after stopTest that have been removed. Record permissions should not be an issue, as the running user should be the owner of all records used in the test. I'm currently in the process of going through all of the UnitTestUtil methods I'm using line-by-line, although I'd be surprised if that was the issue since the test cases were executing successfully prior to using a VF email template.