So it's not just a question of eating varied vegan food as a side-effect of not getting bored with it, but getting enough vegan food that has proteins in it.
Does paleo suffer the same deficiency, i.e. is it simple to be lacking in some specific substances that are pretty vital when following a paleo diet?
B12 is a different issue. I cheat and eat Corn Flakes and plain Cheerios with various types of fortified "milks".
It's certainly possible for a vegan to miss certain amino acids, but it's not as hard as it's made out to be to get them all.
Deficiencies exist in all diets (as they are, by nature, restrictive), the problem is that the extent of these deficiencies is blown way out of proportion. It is very hard to be truly deficient in a vitamin/mineral/amino acid in the privileged western world, but there are a few diets which do mess this up, and vegan is one of them, particularly iron for women.
When you cut out processed foods, and grains, you are left only with pretty much only healthy foods, so it's no wonder they feel better. But that isn't the same as saying all grains and processed foods are bad for you.