I hadn't seen the complico puzzle before. Very interesting.
As for the hexaflexagon, there's some interesting things you can do with it. There's ways to get many more numbers folded into that thing, and with more numbers, some become difficult to find. There's even ways with non-straight pieces of paper to get some non-multiple-of-six numbers of visible panels (like 7 ... that one's weird).
I'll try to describe the way to make larger flexagons with straight strips of paper. I don't remember specifically how long it has to be ... a little planning will make it readily apparent.
Take a long strip of paper and mark off consecutive equilateral triangles for the entire length (I usually just fold to mark them).
Then you're going to "twist" the paper. If you numbered the folds on the paper from left to right, valley fold 2, mountain fold 4, valley 6, mountain 8, etc.... until the strip of paper looks like it has the same number of panels as the simple version (if you do it, you'll understand), then just make the simple version with this twisted piece of paper. I don't know the number pattern, so I'll just suggest trying to make everything show up.
Sorry for the bad instructions, Be prepared for some trial and error.
edit: Found a page that shows how to fold some of the more complex ones.
http://home.adelphi.edu/~stemkoski/math ... xagon.html