You shouldn't need to change the sockets, just make sure the wires are connected to the proper terminals. It sounds as though someone was wiring them up who didn't know or care about whether the hot or the neutral went to the brass or the silver terminal on the socket.
Reversed polarity is primarily an operator safety concern; it won't hurt devices that are plugged in. It will, for instance, mean that a lamp plugged into the outlet will have the outer shell of the light bulb socket hot (even when the lamp is switched off), and can thus pose something of a shock hazard when changing the bulb without unplugging, or even when groping around for the switch if you're particularly unlucky.
Before doing too much, I would check again that the monitor is giving you accurate information. A little neon test lamp would suffice for checking the outlet (or, slightly more sophisticated, a plug-in three light tester that has three indicators mounted together in a plug).
Incidentally, the things on the wall of your house are "outlets" or "sockets." "Plugs" are the gizmos on the end of the electrical cords that get put into the outlets. Usually the difference in words is somewhat immaterial as the proper one can be determined from the context (as in your question), but every once in a blue moon using the wrong one leads to all sorts of confusion.