It could be spots of mould, these can be caused when cold air is trapped behind a picture creating a small amount of condesation on the wall. Just give it a good clean before painting.
If it is the fact the wall is so cold it may well be worth seeing if you can insulate it
.
If this is an inside wall, then bear in mind, I'm only a chippy