Over on the olimex blog http://olimex.wordpress.com/ they recently started a 'weekend programming challenge' series which could be an idea for the parallella project once the boards are available.
What I like about it is that it isn't a competition, it isn't tied down to any language or method, it isn't even judged, and the problems are simple enough to tackle in a short period of time. They're sort of like tutorial or end-of-chapter questions.
I guess the `challenge' with parallella would be coming up with something simple enough to do in a short period of time, but there are a lot of basic algorithmic operations which might fall into that category. It might need a bit more time/run less often but the general idea seems a reasonably soft and fun way to introduce concurrent programming.