For the stills I'd use Photoshop,
a quick method which would give OK results would be: apply the cut-out filter (filters> artistic> cutout), set the no. of levels to the highest (8 I think), then duplicate the layer and apply the find edges filter (filters> stylize> find edges), set the blend mode to multiply on the edges layer and adjust opacity as needed.
Alternatively, you could get an OK result in Premiere (I'm using version 6.0 but I'm sure it'll be similar in Pro/Elements) for the video by using the video effects> stylize> find edges effect, I set the blend with original to about 70%, it looks similar to the effect in that video. (see attached image)
There's no-doubt a fantastic plug-in that does exactly what you want in After effects, but these solutions might be a good start.
Panasonic SD9, Panasonic NVGS-75, Canon MV600i