Okay, so at this point they can do fairly simple programs. The question is "what direction is best at this point?" I would recommend teaching them how to get programs written, rather than fiddly numbers problems - they may need a few of those to feel comfortable, but getting the real tools into their hands: modules, and thinking like a programmer - this is what will be most valuable to them.

If you want to concentrate on programming per se - as in, learning how computer sciency stuff works - I might recommend working through the examples in Kernighan and Plauger's "Software Tools". It's amazing how much meat there still is in that book. You'll need to work with them to recast the problems into Perl - and that may be a very valuable experience for them. Certainly it was for me.

The Cookbook is a great way to move through the spectrum of Perl programming as well, as previously mentioned.

Two things I would emphasize if I were teaching a beginning programming class again would be how to write tests (Test::More and the like) and how to use the debugger. You may want to spend a little time on modules and how they work; you can then show them how CPAN can vastly help them in getting stuff done, possible bringing in Module::Starter.