Why re-label the strand ends in 3' DNA labelling?
There are many ways to label nucleic acids for probes (Summary of Methods). 

While there are cases where Klenow fragment-mediated fill-in should sufficiently label both strands of your probe, there are many others where this would not be enough.  Here are two illustrative, although somewhat contrived, examples:


  Example 1: Double digest with 5' and 3' overhangs
  Imagine you did a double digest with BamHI and KpnI to release your probe sequence from the plasmid in which you propagate the sequence.  BamHI will give you a 5' overhang, but KpnI gives a 3' overhang.

Resulting BamHI & KpnI double digest fragment:
  5'-    GATCCNNNNNNNG      - 3'
             |||||||||
  3'-        GNNNNNNNCCATG  - 5'

  
  Subsequent treatment with the Klenow fragment + $\alpha$P32-dATP + cold dNTPs will both fill-in the 5'-overhang (Klenow's 5'->3' polymerase activity) and remove the 3' overhang (Klenow's 3'->5' exonuclease activity).

Post-Klenow reaction (bold = new bases, * = radio-labeled nucleotide):
  5'-    GATCCNNNNNNNG      - 3'
         |||||||||||||
  3'-    CTAGGNNNNNNNC      - 5'
           *

  
  At this point only one strand is radio-labeled so the terminal transferase step is needed to add a label to the top strand.


When using $\alpha$P32-dNTPs, you often pick only one base to be radioactive (eg dATP as above).  Sometimes you also just spike the reaction with radioactive dNTP leaving a population of cold dNTPs to be used most of the time.  In either case you now have the chance of not incorporating only non-radioactive bases.  


  Example 2: Fill-in reaction that fails to incorporate $\alpha$P32-dATP:
  
  Imagine a digest with PspI and want to fill-in the 5' overhangs using $\alpha$P32-dATP + cold dNTPs.  PspI recognizes CCWGG sequences where W is either A or T so that some fill-ins will incorporate the $\alpha$P32-dATP, but others will not.

Possible digests and fill-in reactions:
   5'-  CCTGGNNNNNNNNNNCCTGG - 3'
        ||||||||||||||||||||
   3'-  GGACCNNNNNNNNNNGGACC - 5'
                 |
         Digest with PspI
                 |
                 V
   5'-  CCTGGNNNNNNNNNN      - 3'
             ||||||||||
   3'-       NNNNNNNNNNGGACC - 5'
                 |
        Fill-in with Klenow + hot dATP + cold dNTPs
                 |
                 V
   5'-  CCTGGNNNNNNNNNNCCTGG - 3'
        ||||||||||||||||||||
   3'-  GGACCNNNNNNNNNNGGACC - 5'
          *
 
  
  Again you are left with only one strand being labeled (or no strand labeling if the sequence was 5'- CCAGGNNNNNCCTGG - 3') and a need for the terminal transferase step.