I think that Colemak would be the best for him. We'll just use my uncles extra Dvorak stickers...
My uncle is quite reluctant, but the statistics don't lie.

What other advice do you think that I could use to help avoid frustration for him?

I wouldn't use stickers. Get him to learn by using a program such as Typefaster which shows the learner which key to press on the onscreen keyboard. You'd be doing him a bigger favour by training him to never need to look at the keyboard.

Edit: And of course Colemak should be the layout.

We all agree (cousin, uncle and I) with simonh that proper typing technique would be good, without looking at the keyboard. Both my uncle and I didn't use the stickers to learn our layouts, (my uncle just put them on for those keyboard shortcuts on Dvorak), so it would be best for him not to use them to learn either. He seems to have figured out how to use the index finger tab things (I don't know what they are called) to get proper position. That should make life easier, so for now he uses the PKL diagram on windows, and a paper diagram on the top of the Linux box, which is exactly what I did when I was learning since I didn't know about the PKL diagram.

So I guess that means another Colemak user is on a journey...
The revolution continues. Thx guys