How about remembering whether you've seen the word 'priority' already, and if so, replacing it, and not replacing it if you haven't seen it at least once already? You have to forget that you've seen 'priority' already if you see an empty line.

open(MYINPUTFILE, "cos2");
$/ = '';
while (<MYINPUTFILE>) {
    while ( /\b([\w'-]+) (\s+\1)+\b/gi ) {
        sed 's/$1/bandwidth/';
    }
}
[download]

Maybe you can tell me where in the Perl documentation you found the sed command?

As a next step, I would recommend that you add comments indicating where you wrote the code that you think implements the steps I outlined for you to undertake.

Also, it often helps us to help you better if you also tell us what the error message is, possibly together with the input data.

A minor note regarding modifying the $/ variable. While it is useful for slurping a file, it is best done with local inside a code block to minimize any possible problems later on in the script. e.g.,

{
    local undef $/;
    while (<MYINPUTFILE>) {
        ...
    }
}
[download]

That way the changes are limited to that block only. Very useful when messing with the special variables.
-----
"Ask not what you can do for your country. Ask what's for lunch."
-- Orson Welles

Here's some pseudocode to help you get started:

while (readline into $line)
  if $line starts with 'priority'
    print $line if 'priority not already seen'
    remember that priority was seen
  end
  else if $line is blank
    forget that priority was  seen
  end
  else
    print $line
  end
end
[download]

while (readline into $line)
  if $line starts with 'priority'
    replace 'priority' with 'bandwidth' if 'priority already seen'
    remember that priority was seen
  end
  else if $line is blank
    forget that priority was  seen
  end
  print $line
end
[download]

It's basically what Corion already said, but it has the basic structure of what your code might look like. Now all you have to do is translate it.

Update: Changed pseudocode to do substitution rather than skip printing.