How about this:

%madname = ( ## Uppercase easy to see in the story file
  "NOUN" => "a noun",
  "VERB" => "a verb",
  "ADJ" => "an adjective");

$storyfile = shift or die "I need a filename!\n";
open(STORY, "$storyfile") || die "Could not open $storyfile: $!\n";
while (<STORY>) {
  push(@lines, $_);
  ## Count total inserted words
  while (m/\[(NOUN|VERB|ADJ)\]/g) {
    $madlib{$1}++;
  }
}
close(STORY);

for $x (sort keys %madlib) {
  for $y (1..$madlib{$x}) {
    print "Please give me $madname{$x}: ";
    chomp($answer{$x.$y} = <STDIN>);
  }
  $madlib{$x}=1; ## reset this
}

## Tricky part...
for (@lines) {
  s/\[(NOUN|VERB|ADJ)\]/$answer{$1.$madlib{$1}++}/ge;
  print;
}
exit;
[download]

As a bonus, you can have more than one "madlib" on a line, like this:

She dropped the [ADJ] [NOUN] and ran into the [ADJ] house.
[download]

You also don't have to worry about numbering them, or keeping a total count - the program does that for you.