The factor of 1/2 is required from Galilean invariance, so that the energy mixes up with the momentum without a factor. This was understood before relativity, but it is largely conventional before relativity, since you could make the energy mix up with the momentum using some coefficient. Once you have relativity, the 1/2 is no longer optional.
I'll start with relativity. The kinetic energy formula is the extra energy in a moving particle
$$ {m\over \sqrt{1-v^2}} = m + {mv^2\over 2} + \cdots$$
in units where c=1. The one half comes from the expansion of the geometrical square root, and the square-root form in the denominator is uniquely and naturally fixed by requiring that the energy and momentum fit together into a four vector. This is the only natural definition in relativity, and it is justified by geometry.
In Newtonian mechanics, the energy and momentum transform together after a Galilean boost. If you have a closed system with momenta $p_i$ that add up to zero (center of mass frame), the change in the kinetic energy after a boost, which shifts $p_i\rightarrow p_i - m_i v$ is
$$\sum_i {p_i^2\over 2m_i} \rightarrow \sum_i m_i~(v_i - v)^2 = \sum_i {p_i^2\over 2m_i} - \sum_i p_i \cdot v + \sum_i m_i {v^2\over 2} $$
The change has two parts,
$$ (\sum_i p_i) \cdot v $$
This is the mixing of energy and momentum, and this part is the total momentum dot the velocity, and it is zero when you start in the CM frame. The other part is:
$$ (\sum_i m_i ) {v^2\over 2} $$
This part is the total mass times half the square of the velocity, or the total kinetic energy added to the object by boosting it. You see that you get the right answer, the total mass times the center of mass velocity, now that the center of mass is moving. If the object was already moving, it is nontrivial to ensure that you get the right answer--- the new center of mass velocity squared times the total mass squared--- for the new energy.
This requirement, that the energy is consistent under galilean boosts, is what is meant by the mixing of momentum and energy. It is simplest if you take the coefficient 1/2, ultimately because this is the natural nonrelativistic limit of relativity. You would have a factor of 2 in the p mixing term if you didn't take the coefficient 1/2. It is actually a testiment to the insight of the 19th century physicists that they adopted the most natural convention before relativity was discovered.
The reason your expectations of kinetic energy loss are violated is because you picked a non-inertial reference frame.
In fact, you didn't notice, but based on your assumptions, momentum isn't even conserved.
Let's look more closely at your first equation:
$$m_e * 0 + m_i v_i = m_e * 0 + m_f v_f$$
Let's say the ball's mass is 5 kg. If the ball is falling down towards the ground, the initial velocity before the collision should be negative (assuming we have adopted a coordinate system where "up" is positive). Let's say the ball was moving at 10 m/s. Here is our equation so far:
$$m_e * 0 + (5 kg) (-10 m/s) = m_e * 0 + (5 kg) v_f$$
Let's simplify, given your assumption that the Earth doesn't move:
$$(5 kg) (-10 m/s) = (5 kg) v_f$$
Which gives us
$$ v_f = -10 m/s $$
Whaaa? The final velocity is negative? That means . . . after this "collision", the ball is still falling downward at the same speed! If we assume, as you did, that the velocity was positive, then the momentum of the system can't be conserved! Clearly, something is wrong here.
Here's the trouble: You began in the reference frame of the Earth. Once the ball hit the Earth, the Earth's reference frame is no longer inertial! You either have to introduce a fictitious force on the ball to account for the fact that the Earth accelerated (a tiny bit, yes, but an important tiny bit), or you need to find an inertial reference frame.
So, Let's pick the frame of reference in which the Earth starts out at rest. When the Earth moves, we'll let our frame of reference stay where it is, so as to allow it to remain inertial:
$$m_e * 0 + (5 kg) (-10 m/s) = m_e * v_{e, f} + (5 kg) v_f$$
$$-50 kg m/s = m_e * v_{e, f} + (5 kg) v_f$$
NOW we can introduce a coefficient of elasticity and demand that energy be either conserved or not, and find the final velocity of the Earth and the ball as they rebound from each other.
Note that although $v_{e, f}$ will be incredibly tiny, due to the enormous mass of the Earth $m_e$, the final momentum of the Earth will be non-negligible - in fact, the final momentum of the Earth must be comparable to the final momentum of the ball in order for momentum to be conserved!
So, to sum up: You picked a non-inertial reference frame, and didn't account for it, so your reliance on the laws of physics was betrayed.
Best Answer
Starting with
$$T = T_{cm} + \sum m_iv_iv_{cm} - \sum\frac{1}{2}m_iv_{cm}^2$$
use
$$v_{cm} = \frac{\sum m_iv_i}{\sum m_i}$$
which can also be written as
$$\sum m_iv_i = v_{cm}\sum m_i$$
and substitute back in to get
$$T = T_{cm} + \sum\frac{1}{2}m_iv_{cm}^2$$