I would do this by making an array of hashes. Your "headers" would become the keys of the hashes. Then push them on an array when you are done. Like this:

use strict;
use warnings;
use Data::Dumper;

my @Values;
my $HashSet = ();

while(<DATA>)
   {
   chomp();
   (my $Header, my $Value) = split /: /, $_, 2;
   $HashSet->{$Header} = $Value;

   if($Header eq 'Waiting')
      {
      push(@Values, $HashSet);
      $HashSet = ();
      }
   }

   print(Dumper(@Values));

__DATA__
Update Time: 2005.04.27 15:44:12
Targets: 4
Complete: 4(100%)
Waiting: 0
Update Time: 2005.04.27 15:45:10
Targets: 10
Complete: 5(50%)
Waiting: 5
Update Time: 2005.04.26 12:15:08
Targets: 3
Complete: 1(33%)
Waiting: 2
[download]