I'm going to try to hit on several things here that may or may not prove fruitful for you. First, from the Winter 14 Apex Code Developer's Guide:
setSaveAsActivity(Boolean)
Optional. The default value is true, meaning the email is saved as an activity. This argument only applies if the recipient list
is based on targetObjectId or targetObjectIds. If HTML email tracking is enabled for the organization, you will be
able to track open rates.
setTargetObjectId(ID)
Required if using a template, optional otherwise. The ID of the contact, lead, or user to which the email will be sent. The ID
you specify sets the context and ensures that merge fields in the template contain the correct data.
Signature
public Void setTargetObjectId(ID targetObjectId)
Parameters
targetObjectId
Type: ID
Return Value
Type: Void
Usage
Do not specify the IDs of records that have the Email Opt Out option
selected. All email must have a recipient value of at least one of the
following:
• targetObjectIds
• toAddresses
• ccAddresses
• bccAddresses
• targetObjectId
Are your recipients valid contact ID's? I'm assuming they are and that when you tested, you set the IsActive flag on them to true.
setHtmlBody(String)
Optional. The HTML version of the email, specified by the sender. The value is encoded according to the specification
associated with the organization. You must specify a value for setTemplateId, setHtmlBody, or setPlainTextBody. Or, you can define both setHtmlBody and setPlainTextBody.
Email Template
A form email that communicates a standard message, such as a welcome letter to new employees or an acknowledgement
that a customer service request has been received. Email templates can be personalized with merge fields, and can be
written in text, HTML, or custom format.
I notice you're using a VisualForce template. Have you attempted resolving your problem by using an HTML or Text based template instead? Your problem could easily be related to a problem in your VisualForce that wouldn't at all be apparent.
Another thing that may be of relevance to your issue is the following:
EventRelation allows a variable number of relationships, as follows:
If you’ve enabled Shared Activities for your organization, an event can be related to up to 50 contacts or one lead. If you haven’t enabled Shared Activities, an event can be related to only one contact or lead.
An event can also be related to one account, asset, campaign, case, contract, opportunity, product, solution, or custom object.
TaskRelation allows a variable number of relationships, as follows:
A task can be related to one lead or up to 50 contacts.
A task can also be related to one account, asset, campaign, case, contract, opportunity, product, solution, or custom object.
Available in API versions 24.0 and later. Available only if you’ve enabled Shared Activities for your organization.
Have you enabled Shared Activities for your org? If not, that could be at the root of the issue you're having. In essence, the TargetObjectid is the WhoID and the RelatedToType is the WhatID of your email/activity. I see from what you've posted above that you've specified both the RelatedToType and the WhatID. That in itself may very well be the actual source of your problem.
Finally, if this doesn't help you resolve your issue, I'd highly recommend you post a copy of the gist of your template that includes all of the fields (please remove any confidential or identifying information). Its possible there's something about a field you're using in it that's creating a conflict which isn't readily obvious.
setTargetObjectIds(ID[])if you want to do multiple records and save activities?