Nevermind that in the end it's going to end up in a 600 line script. Show us the code you wrote for this small, self-contained task.

Therein lies my problem, I've got nothing. sed will replace every occurance, grep will find me every occurance. What I need is something to get me started, that will find/replace all occurrances of the word 'priority' except the first one in each paragraph. I had even considered condensing each paragraph into one line and potentially doing it from there, but even then I would still have the same issue. I'm completely out of ideas, don't know how to even start.

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.

Ok, so I've found this online, but i keep getting compilation errors. At any rate, do you think this is something I can build on to do what I'm trying to accomplish?

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

I really appreciate the help on this, it's been driving me crazy.

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.

use strict;
use warnings;

while (<DATA>) {
    if (/^Class voip/ .. /^\s*$/) {
        s/priority/bandwidth/;
    }
    print;
}


__DATA__
Class control
priority 5
Class voip
priority 30
Class video
priority 40


Class control
priority 10
Class voip
priority 25
Class video
priority 45
[download]

Class control
priority 5
Class voip
bandwidth 30
Class video
bandwidth 40


Class control
priority 10
Class voip
bandwidth 25
Class video
bandwidth 45
[download]

Read the file in paragraph mode as others have suggested then process each paragraph by spliting into words and the separating whitespace (by capturing the whitespace you split on), doing the substitution when appropriate.

use strict;
use warnings;

open my $inFH, q{<}, \ <<EOD or die qq{open: <<HEREDOC: $!\n};
Class control
priority 5 
Class voip
priority 30 
Class video
priority 40 


Class control
priority 10 
Class voip
priority 25 
Class video
priority 45 
EOD

{
    local $/ = q{};
    while( <$inFH> )
    {
        my $foundPriority = 0;
        $_ =
           join q{},
           map {
                   unless( m{\bpriority\b} )
                   {
                       ;
                   }
                   elsif( $foundPriority ++ )
                   {
                       s{priority}{bandwidth};
                   }
                   else
                   {
                       ;
                   }
                   $_;
               }
           split m{(\s+)};
        print;
    }
}

close $inFH or die qq{close: <<HEREDOC: $!\n};
[download]

The output

Class control
priority 5 
Class voip
bandwidth 30 
Class video
bandwidth 40 

Class control
priority 10 
Class voip
bandwidth 25 
Class video
bandwidth 45
[download]

I hope this is useful.

use strict;
use warnings;

while (<DATA>) {
    if (((/^priority/ .. /^\s*$/) || 0) > 1) {
        s/priority/bandwidth/;
    }
    print;
}


__DATA__
Class control
priority 5
Class voip
priority 30
Class video
priority 40


Class control
priority 10
Class voip
priority 25
Class video
priority 45
[download]

You don't say how the data is held (In a scalar? An array of lines? In an unopened file?), but you and others are going with processing a file line-by-line, which generalizes nicely to processing an array, so I'll take that approach.

use warnings;
use strict;

my $bol_priority = qr{ \A priority }xms;  # 'priority' begins a line
my $blank_line   = qr{ \A \s* \z   }xms;

my $saw_priority = '';

while (<DATA>) {

    s{ $bol_priority }{bandwidth}xms if $saw_priority;

    $saw_priority = /$bol_priority/ .. /$blank_line/;

    print;

    }

__DATA__
Class control
priority 5
Class voip
priority 30
Class video
priority 40


Class control
priority 10
Class voip
priority 25
Class video
priority 45
[download]

Class control
priority 5
Class voip
bandwidth 30
Class video
bandwidth 40


Class control
priority 10
Class voip
bandwidth 25
Class video
bandwidth 45
[download]

while (<FILE>) {
    # set modification flag to 0
    my $do_mod = 0;
    if ($do_mod) {        # if modification flag is true (>0)
        # apply substitution if matches
        s/priority/bandwidth/g;
        # if line is empty, clear modification flag
        $do_mod = 0 if (/^$/);
    } else {
        # Found first priority, mark modification flag true
        $do_mod++ if (/priority/);
    }
    print;
}
[download]

I don't think that code does what you think it does.

It prints to STDOUT instead of inline editing, but that's an easy redirect. Otherwise, it works just fine on my end.
-----
"Ask not what you can do for your country. Ask what's for lunch."
-- Orson Welles