
Have they got frozen ground outside? I've been amazed at how hard and frozen the ground has been. Also, you could check that if they have frozen ground, that they haven't been spreading salt around. A combination of hard spiky ground and salt used to melt ice would almost certainly cause problems with a pup's soft pads.
Other than that, I'd tend to agree with what others have suggested, i.e. cleaning products used on floors.
Hope they get to the bottom of what's causing the problem...