Can you not deploy a new VM from the template, migrate that VM to the new datastore, then convert that new VM back into a template?
Something like:
> $newVM = Get-Template "template-name" | New-VM
> $newVM | Move-VM -Datastore (Get-Datastore "destination-datastore-name")
> $newVM | New-Template
Just a thought.