by chance, did you replace the one dimmer that actually worked by accident, instead of replacing one of the bad ones?
i know that is a silly question but the dimmer/switch is what controls the lamps. the fixtures themselves, are just fancy connection points with reflectors for the lamps... the switch does all the 'work' as far as controlling the lights. if you lost the capability to dim, than the problem is definitly in the box.
now if your lights come on for a short period, then cutoff for no apparent reason, most recessed can lights have thermal overload switches built into them, so that if the lamp gets too hot, the fixture will cut off. if the power is shut off for 10-15mins, usually the fixture will cool down enough so that thelight comes back on... if thats the case, either get R20 floods (there cooler) instead of PAR halogen lamps, or switch to a lower wattage lamp.
but if what is happening is that the lights will come on or come off, but wont dim, either you have bad dimmers, cfl lamps installed (floro's do not dim, unless you have a special ballast with special wiring) or your replacement dimmer is not wired correctly.
some solid state dimmers (digital, often have LED indicators) are line/load sensitive, in other words, there is a specific connection for the 120v incoming line, and a specific connection for the load that is to be switched. some of these dimmers also require a neutral, and some of them require that at least one working lamp be installed on the circuit. so if your 4 lamp switch is working, and your 2 2lamp switches are not, check to make sure you got working lamps in those fixtures before you tear your walls apart.