The difference between heat and temperature So as I understand it, heat energy of an object is the SUM of all the kinetic 
energies of the molecules of the object (up to constant factor). 
The temperature on the other hand is the AVERAGE of the kinetic energies of all 
the molecules of the object.   
Now when ice is melting at $0\,^\mathrm o$C, the temperature as measured on a 
thermometer does not go up. 
The common explanation is that any heat being absorbed by the ice is being
used to break the somewhat strong solid bonds between the molecules of the 
ice. 
Here is my question. If heat of an object is what I defined above, then since 
all the molecules are increasing in kinetic energy, the average of the kinetic energy should also increase, meaning the temperature should increase. But at 
$0\,^\mathrm o$C for ice that does not seem to be the case.
Where am I going wrong in my understanding?
 A: The kinetic energy of the atoms is only the nuclear part of the internal energy. The electronic structure responsible for chemical bonds is another part. 
Any heat used to change the electronic structure (i.e., breaking bonds) does not affect the kinetic energy of the atoms.
A: Heat is not a property of a system. Heat is a process function. Temperature is a property of a system because is a state function. For instance, the state of a simple gas is given by temperature, pressure, and composition $(T,p,N)$.
Temperature is defined as the inverse ratio of variation of entropy $S$ to changes in internal energy $U$
$$T \equiv \left( \frac{\partial S}{\partial U} \right)^{-1}$$
This is the thermodynamic concept of temperature, which is more general than the kinetic concept that you are considering. Regarding your question, part of the energy given as heat is used to break the bonds and when are broken if you continue supplying energy this will increase the kinetic energy of the molecules.
Moreover, kinetic temperature is not the average of the kinetic energies of all the molecules of the object. This average of kinetic energies is the average kinetic energy. The kinetic temperature is defined as $2/3$ the average internal energy per number density.
At the other hand, heat $Q$ is defined for a given process as the internal energy interchanged which is neither work nor due to flow of matter
$$Q \equiv \Delta U - W - U_{matter}$$
Notice that internal energy is a state function and $\Delta U$ denotes the difference between the initial and final energies, but heat is not a state function and this is why we write $Q$ instead of an incorrect $\Delta Q$.
The concept of process function is most easily understood with the example of a lake. A lake has some amount of water, and this can change by evaporation and raining. You can count the amount of water added to the lake by some raining process, but the lake itself does not have any amount of "raining" or evaporation" only some amount of water. Similarly a thermodynamic system has internal energy but has not heat or work.
A: Why does temperature of ice not increase when heat is supplied to ice?
Breaking of hydrogen bonds when ice melts is an endothermic reaction.
Energy in the form of heat is absorbed to break the hydrogen bonds in this reaction.
Kinetic energy of molecules does not increase. 
But the internal energy of the ice/water increases.
source: http://en.wikipedia.org/wiki/Ice 
(see characteristics)
A: A different perspective might help to clear the confusion: 
The average does not have to change. During melting you just "add" molecules to the liquid part of your system. While the number of water molecules increases, the temperature during this process and the kinetic energy of the individual molecules stays constant. Only if all ice is melted away all molecules are in the same thermodynamic phase. The energy is used up to break the bonds. 
Now heating up the system further increases the average of the kinetic energy. So there is not really a paradox here and your descriptive definition is not wrong either. You only neglected that this is a first order phase transition with two different phases of matter co-existing.
A: An object (system) doesn't pocess heat energy, but it is said to have internal energy. When the object (system) is an ideal mono atomic gas, the internal energy is same as the sum of kinetic energy of the atoms. Energy is an extensive quantity. That means the value of the internal energy depends on the extent (here number of atoms) and is proportional to the number of atoms. Temperature on the other hand is an intensive property and does not depend on the extent of the system. 
An ideal gas by definition, has only kinetic energy and it is its internal energy. For a closed system of  ideal gas the temperature can not increase/change without the internal energy increase/change.
However, in the case of melting ice, the ice-water closed system has potential energy, besides kinetic energy of atoms. In such complex systems the internal energy is not related in a simple way to temperature of the system. For example, as in the case you consider - where a process brings about a phase change  in a closed system - addition of heat to the system does not bring about a change of temperature. Here the internal energy changes but the temperature does not change. 
Again, even in the case of a closed ideal gas system, if addition of heat is accompanied by a reversible expansion of the ideal gas, the temperature of the system does not change. Here the internal energy does not change, and the temperature also does not change - in spite of the fact that heat is added to the system.  
A: juanrga gave a correct answer. I will add some further help to pin-point precisely where your reasoning went wrong. I will quote each part of the question and react.

So as I understand it, heat energy of an object is the SUM of all the
  kinetic energies of the molecules of the object (upto constant
  factor).

This part is using terminology incorrectly, and forgetting some of the energy contributions. You should have said:
"Internal energy of an object is the SUM of all the kinetic energies and other energies of the molecules of the object."

The temperature on the other hand is the AVERAGE of the kinetic
  energies of all the molecules of the object.

This is roughly ok. It is not quite the exact average (divided by a universal constant) but it is often of that order.

Now when ice is melting at 0 degrees Celsius, the temperature as
  measured on a thermometer does not go up.
The common explanation is that any heat being absorbed by the ice is
  being used to break the somewhat strong solid solid bonds between the
  molecules of the ice.

All true.

Here is my question. if heat of an object is what I defined above,
  then since all the molecules are increasing in kinetic energy, the
  average of the kinetic energy should also increase, meaning the
  temperature should increase. But at 0 degrees celsius for ice that
  does not seem to be the case.

You should have said:
"If internal energy of an object is what I defined above, then since all the molecules are increasing in energy, the
average of the total energy should also increase. But I notice that the temperature is not increasing. This suggests the kinetic energy is not increasing either. Oh, I see: it could be that the kinetic energy of the molecules is not changing in this example, but their potential energy is changing, and this does not affect the temperature. So whereas there is quite a close relationship between kinetic energy and temperature, the potential energy of the molecules can sometimes be unrelated to the temperature."
If you had said that, you would not have gotten in a muddle. The potential energy here is the fact that if molecules attract one another, then when they are further apart they have more potential energy than when they are close together.
Finally, the strict relationship between temperature and energy is via the entropy. But I decided not to get into that.
A: Your statement in the question as the starting point: heat energy of an object is the SUM of all the kinetic energies of the molecules of the object. But we can see this as incomplete definition,particularly in solids where Heat energy is divided in two parts:
 i-Kinetic energy of molecules which causes heat transfer by conduction and
 ii-Potential energy of molecules in solid structure due to short range molecular forces which acts as a store of heat energy.This store of heat energy appears in the process of melting (material gains heat energy) or solidification (material looses heat energy )   
The temperature on the other hand is the AVERAGE of the kinetic energies of all the molecules of the object which is true and that is the reason why the other part of energy is called hidden or latent heat.
Your explanation  that any heat being absorbed by the ice is being used to break the somewhat strong solid bonds between the molecules of the ice  is also true but you should add that this heat is not lost ,but stored in the melt as potential energy.In your case nothing is left to raise the average of the kinetic energy of molecules.
The miss understanding stems from your incomplete definition .The heat of an object is not exactly what you defined above. 
A: heat is the total kinetic energy possessed by all randomly vibrating particles of a body.
heat is an energy as well as process function.It cause the temperature to increase.
Temperature is the average rate of vibration of particles due to heat.It is a unit as well as state function.It is measured by the help of themometer.
A:                      *HEAT*

.Heat is form of invisible energy,which is a sensation of hotness or coldness.
.Heat flows from higher to lower temperature body.
.Heat is measured with calorimetre.
.SI unit of heat is joules
      TEMPERATURE
.Temperature is a physical quantity that have thermal equilibrium of both bodies.
.Temperature is a degree of hotness or coldness  of a body.
.it is measured with thermometer
.SI unit of temperature is kelvin
