Just to note about using the map generator, in case you were unaware, in order for it to accurately give you a map based on your currently existing seed, you have to upload your world files (the blue upload button next to the text box); it provides instructions for this. If you just enter your seed code (number?), it generates a map under the assumption it's a brand new, completely unexplored world, which is why you would be seeing frost cave markers on the generated map but not finding any in your world.

Also, if you have unexplored mountains, but have explored the area surrounding them - PRIOR to the update - the actual world generation area is much larger than what is revealed by the player. This means the mountain could have already been fully generated before the patch and thus wouldn't be able to update to spawn caves.
There is a mod, Upgrade World, that can regenerate the mountain biome and enable the caves to spawn. Obviously you'd use this at your own risk and you'll want to be sure to backup your world files beforehand. I've used it for this with no issues so far.