The cloning process is 'blind' to the sequence of the insert to be cloned therefore the length of sequence present before or after the gene is irrelevant.  The only thing you really need to consider is how much sequence you have between your 3' and 5' restriction sites and the ends of the PCR fragment.  10 pb should be enough to enable efficient restriction but you should check first as this is different according to which enzymes you are using (New England Biolabs should have this info)

Sorry, maybe I did not put  it really clearly, I was wondering if different overhang length has an effect on pcr performance.

If I have understood it, you want to use a primer that have 75pb out of the sequence you are trying to clone?? from my point of view that is almost impossible, since the inespecific binding its gonna be crazy high. It should be better if you make the cloning in two steps adding the synthetic terminator to the sequence after purify the sequence.

About the differences of overhang length in both primers, be carefull, since they will have differents Tm in the differents cycles of the PCR so you would need to check both Tm, with and without the overhang of each primer and try to make it similar.

Yeah, that sounds too long.  Also a terminator has secondary structure, which you should generally avoid in your primers. You should order a synthetic gene for this and clone it using whatever your favorite technique may be. 

1. If you want to use primers to add a 'restriction site (RS)' and 'terminator-restriction site' to your gene 5' and 3' ends, your primers will look like this:

(1) Forward primer: [RS1-(primer sequence)]

(2) Reverse primer: [(primer sequence)-(terminator, 75 bp)-RS2]

If the primer sequence is around 20 bp and RS is around 6 bp; then, your F-primer will have around 26 bp and your R-primer will have around 101 bp. The Tm for these two primers will be extremely different and will cause trouble for you setting the annealing temperature.

2. So, I agree with David, you can try 2-step cloning. First, clone in your gene-of-interest and at the 3'-end of your gene create an unique RS3, which can be used to clone in the 75-bp Terminator (with RS3 at the ends).later.

Sorry Martin I misunderstood your question.  If your template DNA is the gene of interest in a vector (i.e. not a cDNA library or genomic) then for the cost of a primer I think it would be worth giving it a go.  The possible occurance of non-specific binding of a significant part of the the 75+ bp of the terminator sequence (such that the 5' end of the primer will bind and enable extention) within the 8-9 kbp of the plasmid will not be that great.  In the first round of the PCR only the annealing temperature of the compatible part of the reverse primer will be crucial (Unless of course as John rightly points out, the secondary structure of the terminator inhibits annealing of the in the primer in the first instance).  I know it might sound counter intuitive but if you increased the length of the foward primer such that it's Tm was approaching 70 deg C you might be able to increase strigency and reduce secondary structure issues by cycling between 95 and 72 deg C without an annealing step as such.  As I say considering the small cost of a primer and the extra effort of a two step cloning process at least trying this in parallel might yield quicker results.