That is an amazing video!
I have a friend that is incredible with MS Paint. (much different style though)
She tried the Paintshop Pro installed on my pc once. It made her cry...too complicated. She prefers MS Paint.
This is a self portrait she did with nothing but Paint and a mouse (no sketch to base it on, like was used in that video):http://cecilski.livejournal.com/145344.html
She says it took about one hour to complete.
There are a bunch more portraits she did of other people posted somewhere in her journal, but I can't seem to find them right now.
And just so you know how much it really resembles her, here is a photo of her that was taken by my daughter:http://www.renderosity.co...mage_id=208254&member