Are you meaning the grout seams are breaking down? Or are the tiles themselves separating from the slab? If the tiles are coming loose, is it because of moisture through the concrete is lifting the bond? You say it may be due to the recent cold temps....any chance of insulating the footings around that slab? Using a 3" rat wall shovel against the wall, you could make a neat trench about two foot down and lay in some of that 2" thick pink styrofoam. Cut a 4x8 in half and lay down the eight foot lengths and set the dirt back against it. 'Coarse ya'd have to wait for the spring thaws!!

Using something different than the grout would/could be a different color and texture and may not be aesthetic.