I'm assuming that some (but not all) of the open strings go sharp, and not that they are in tune when open and play sharp when fretted. If the assumption is right:
One possibility is the strings which go sharp are binding in their nut slots. You tune up to pitch, but because the string sticks in the slot there is extra tension between tuning peg and nut. When you play, the strings move in the nut and the tension equalises = higher tension on the playing side and thus the string goes a little sharp.
Were these a different kind of string from those they replaced? If so, they could be a fraction fatter.
You might fix this by putting graphite in the nut slots (pencil lead, just sharpen a pencil and get some pencil marks inside the slots). Graphite is a lubricant which won't hurt your strings. It wouldn't hurt to try this.
The other fix is to widen the nut slots slightly or, better, get someone experienced to do this for you, as you can make things bad pretty quickly if you don't know what you are doing!
Or it might just be the type of string. Aquila Nylguts do this to me - I tune, strum for 30 seconds or so, and then have to perform a final retune, and I know they are not sticking in the nut slots because i use a zero fret.