Actually the article you link to does not says that a balanced Feistel cipher is less secure than an unbalanced one; it says that the security of an unbalanced Feistel cipher is more easily proven, given enough rounds.
Luby and Rackoff have shown in 1988 that a balanced Feistel scheme with only 4 rounds is "perfectly" secure as long as the round functions are "random enough". This deserves clarification: Luby and Rackoff use n-bit blocks, and their results holds up to, at least, 2n/4 queries (the attacker is allowed to submit up to that number of blocks to encrypt or decrypt to a black box which knows the key, and yet he still cannot predict the encryption or decryption of another value with non-negligible probability). Maurer and Pietrzak, and then Patarin, later showed that with more rounds, one can get as close as wanted to the 2n/2 limit (6 rounds suffice, as Patarin demonstrated). (Of course, "random enough" round functions are ideal objects whose existence is not clear; existing Feistel-based ciphers use faster functions which are certainly not "random enough", and compensate by adding more rounds.)
By making n big enough, 2n/2 is large enough to achieve sufficient security (e.g. use n = 256).
Morris, Rogaway and Stegers study the problem of encrypting very small blocks; thus, they cannot make n "large enough". They must cope with a small n. The maximum theoretical security of a Feistel scheme (balanced or not) is 2n-3 queries (there are 2n possible block values; if the attacker knows the encryption of all save two, then he can guess the remaining two with 100% accuracy, because Feistel schemes are always even permutations; this is the only known structural weakness of Feistel ciphers). The authors say quite clearly (end of page 4) that there is no known practical attack on a Feistel cipher with enough rounds, even with small blocks, so the 2n-3 security limit is in practice achieved. But they want more than practical security, they want proven security. A security proof works by assuming that the round functions are information-theoretically secure, and sees how the whole cipher stands up under that assumption. The trouble with a balanced Feistel cipher is that such proofs cannot go beyond 2n/2.
On the other hand, with an unbalanced cipher and many rounds (much more than 6; figures in the article go to about 64 rounds), it is possible to get a security proof close to 2n. This does not mean that unbalanced Feistel ciphers are "more secure", only that information-theoretic tools are more easily applied for proving security of an unbalanced Feistel cipher. And a single unbalanced round is certainly not more secure than a single balanced round; quite the opposite: security-wise, a single unbalanced round sucks. But if you accumulate enough such rounds, then you can boost the security proof to higher levels.