I'm having problems understanding the following situation. Suppose two 1-tonne cars are going with the same orientations but opposite senses, each 50 km/h with respect to the road. Then the total energy is 

$$\begin{eqnarray}E=E_1+E_2&=&\frac{1\mathrm t\times(50\mathrm{km}/\mathrm h)^2}2+\frac{1\mathrm t\times(50\mathrm{km}/\mathrm h)^2}2\\&=&1\mathrm t\times(50\mathrm{km}/\mathrm h)^2\\&=&2500\frac{\mathrm t\times\mathrm{km}^2}{\mathrm h^2}.\end{eqnarray}$$

Now if we look at it from the point of view of one of the cars, then the total energy is 

$$\begin{eqnarray}E=E_1+E_2&=&\frac{1\mathrm t\times(0\mathrm{km}/\mathrm h)^2}2+\frac{1\mathrm t\times(100\mathrm{km}/\mathrm h)^2}2\\&=&\frac{1\mathrm t\times(100\mathrm{km}/\mathrm h)^2}2\\&=&5000\frac{\mathrm t\times\mathrm{km}^2}{\mathrm h^2}.\end{eqnarray}.$$

I know that kinetic energy is supposed to change when I change the frame of reference. But I understand that then there must be some other kind of energy to make up for it so that the energy in the system stays unchanged. But I don't see any other kind of energy here. I only see two total energies of the same system that seem to be different. Could you explain this to me?

Please note that while I don't understand any physics, I do understand college level mathematics, so if necessary please use it. (I doubt anything more than high school maths should be needed here, but I want to say this just in case.)

You have successfully discovered that the kinetic energy depends on the reference frame.
That is actually true.  What is amazing, however, is that while the value of the energy is frame DEpendent, once you've chosen a reference frame, the law of conservation of energy itself is NOT reference frame-dependent -- every reference frame will observe a constant energy, even if the exact number they measure is different.  So, when you balance your conservation of energy equation in the two frames, you'll find different numbers for the total energy, but you will also see that the energy before and after an elastic collision will be that same number.
So, let's derive the conservation of energy in two reference frames.  I'm going to model an elastic collision between two particles.  In the first reference frame, I am going to assume that the second particle is stationary, and we have:
$$\begin{align}
\frac{1}{2}m_{1}v_{i}^{2} + \frac{1}{2}m_{2}0^{2} &= \frac{1}{2}m_{1}v_{1}^{2} + \frac{1}{2}m_{2}v_{2}^{2}\\
m_{1}v_{i}^2 &= m_{1}v_{1}^{2} + m_{2}v_{2}^{2}
\end{align}$$
to save myself time and energy, I'm going to call $\frac{m_{2}}{m_{1}} = R$, and we have:
$$v_{i}^{2} = v_{1}^{2} + Rv_{2}^{2}$$
Now, what happens if we shift to a different reference frame, moving to the right with speed v?  This is essentially the same thing as subtracting $v$ from all of these terms.  We thus have:
$$\begin{align}
(v_{i}-v)^{2} + R(-v)^{2} &= (v_{1}-v)^{2} + R(v_{2}-v)^{2}\\
v_{i}^{2} -2v_{i}v + v^{2} + Rv^{2} &= v_{1}^{2} - 2 vv_{1} + v^{2} + Rv_{2}^{2}-2Rv_{2}v + Rv^{2}\\
v_{i}^{2} -2v_{i}v &= v_{1}^{2}- 2vv_{1} + Rv_{2}^{2}-2Rv_{2}v\\
v_{i}^{2} &= v_{1}^{2} + Rv_{2}^{2} + 2v(v_{i} - v_{1} - R v_{2})
\end{align}$$
So, what gives?  It looks like the first equation, except we have this extra $2v(v_{i} - v_{1} - R v_{2})$ term?  Well, remember that momentum has to be conserved too.  In our first frame, we have the conservation of momentum equation (remember that the second particle has initial velocity zero:
$$\begin{align}
m_{1}v_{i} + m_{2}(0) &= m_{1}v_{1} + m_{2}v_{2}\\
v_{i} &= v_{1} + Rv_{2}\\
v_{i} - v_{1} - Rv_{2} &=0
\end{align}$$
And there you go!  If momentum is conserved in our first frame, then apparently energy is conserved in all frames!
