I went through a similar experience a couple of years ago at a client, bringing C programmers up to speed on Perl. The most important thing to keep in mind is that it will take time. No matter how good the material they're learning from, no one will start using Perl idiomatically until they write several good-size chunks of code. Don't be in a hurry (and see if you can convince your boss of that!)

That said, one thing I found particulary useful was the points in the "perltrap" document that were aimed at C, awk, and shell programmers. These people had worked with all three (Korn shell) and seemd to stumble on every single one of these.

Another area that really helped was talking about loops, labels, and blocks. For that I just used some examples straight out of perlman:perlsyn, particularly the section on foreach loops. Those really seemed to resonate with people.

One exercise that made the light bulb go on for a lot of people was emphasizing how, in Perl, you could manipulate an array rather than use indices into it. My example was: given an array of integers, calculate the sum of the elements doubled. First I showed a "typical" C-ish solution:

# suppose @myvec is an array of integers.
my $sum = 0;
for (my $i = 0; $i < scalar(@myvec); $i++)
{
    $sum += 2 * $myvec[$i];
}
[download]

Next I got a little more Perl-ish:

my $sum = 0;
foreach my $i (@myvec)
{
    $sum += 2 * $i;
}
[download]

That got a few "Aha"s. The next step got some puzzled looks:

my $sum = 0;
$sum += 2 * $_ foreach @myvec;
[download]

But once I explained the $_ and foreach modifier, people were nodding. I probably should've stopped there. In hindsight, it was a mistake to show this next step, which just got people groaning: $sum = eval join('+', map { 2 * $_ } @myvec);As you said yourself, there's no point in prepping people for golf tournaments....

HTH