The problem is that in modern science and chemistry, we've found that these 4 things (water, fire, air, and earth) are not very similar, and by no means all-encompassing categories, so they there's no neat way to define them in similar ways. Because of this, you're going to have to choose if you want to stick close to the ordinary meanings of these terms, and have individual and somewhat arbitrary criteria for each element, or if you want to use the classical elements as a metaphorical basis for a more systematic classification (like in the "states-of-matter" example you give) and have the users be controlling things that don't correspond to our everyday definitions of these four things. You can't have it both ways.
In the rest of this answer, I'm going to outline the most effective individual and arbitrary physical criteria for each element that I think would get you closest to the everyday definitions.
Water = H20. This one is simple, since it is the only one that is a defined chemical compound with essentially a homogeneous composition. Usually in these kind of setups, water-users can also manipulate ice and water vapor, but if you don't want them to be able to you can just restrict their control to liquid water.
Fire: one of the things we have learned is that fire is not a substance. It is a process. In general, fire is characterized physically by the chemical process of oxidation, and the release of energy (exothermy). Clearly, fire also has a close connection, both physically and metaphorically, with heat.
So a fire-user might be able to control things like oxidation and heat-transfer. One interesting fact is that only gases, not solids and liquids, are capable of sustaining a flame. When something solid or liquid appears to burn, it is really being vaporized and then the vapor is what catches on fire. [Edit: vaporization does occur for burning solids and liquids, but the overall situation seems to be more complicated than I originally stated in this post.]
Air: The most obvious criterion you can use for "air" is simply "substance in the gas state of matter". Earth's atmosphere is mostly composed of nitrogen and oxygen molecules, which are two distinct chemical elements that otherwise don't have any special connection, and that can also be found incorporated in solids and liquids, so it's impossible to define air in terms of chemical composition. This could possibly overlap slightly with water-users with regards to the substance of water vapor; you'd have to decide how to resolve that. I suppose you could restrict "Air" manipulators to control of monoatomic and homonuclear diatomic gases: this is a bit arbitrary, but it would include nitrogen, oxygen and argon (the 3 most common atmospheric gases), as well as a number of trace gases, and exclude water vapor (and also CO2; I don't know if that would be a problem).
Earth: this one is the hardest to define, as it's rather vague. However, in general, rocks are composed of minerals, which are solids with an ordered crystalline structure that are inorganic in composition (the chemistry definition of this is a bit tricky, but it basically means that the structure doesn't contain carbon backbones). An earth-manipulator might have the power to affect only things with these kinds of crystalline structures. (As with air, this would lead to overlap with water-users, in this case for the category of ice; you'd have to decide which way you want to assign it.)
You can see that each element has a different type of definition. I don't know if this has to be a downside: if you emphasize how the elements contrast rather than how they fit together, this could inspire some unique extensions for each type of power (for example, fire manipulators might gain the ability to manipulate their metabolisms, since this involves a different type of oxidation, while air manipulators might gain the ability to use sonic attacks, and earth manipulators might gain the ability to change the molecular-level structure of crystalline solids, like turning graphite to diamond).