In the UK, houses use what are called 'ring' mains. Think of it this way. On each floor of the house, the electricity goes in a loop through all of the sockets and back to the distribution board. It doesn't actually work that way but imagine you drew a circle with the board at the bottom and all of the sockets on the circle coming back round to the board.
So say the ground floor has twenty sockets on it. There will be twenty two lengths of wire forming the circuit, joining the board and all of the sockets together in a loop. The electricity powering your stereo passes through the terminals on every other socket in the loop!
Over time the connections in the sockets can deteriorate. The cables can oxidize and the screws can work loose, don't ask how that can happen, but it can! That is assuming they were done up properly in the first place. When I checked the wiring in the house we live in I found not just loose screws but fittings with missing screws! The fitter had obviously lost the screw and just shoved the wire in the hole. That was on the lighting circuit, you wouldn't get away with that bodge on the sockets.
If you replace all of the sockets the act of removing and refitting them could improve the connections in the ring and result in the difference you heard. You're not just talking about one connection but dozens. Some people, myself included, have fitted a 'spur' to supply their Hi-Fi systems. That means a straight run of unbroken cable from the board to the stereo, complacently bypassing the ring with all its joints. The effect is probably similar to what you are hearing but bigger.
As you've just found out, anything you do which improves the electrical connections in your system can and usually does improve the sound.